Similarity-based Reasoning in Qualified Logic Programming
Revised Edition
Rafael Caballero

Mario Rodrı́guez-Artalejo

Carlos A. Romero-Dı́az

arXiv:1008.3867v1 [cs.LO] 23 Aug 2010

Departamento de Sistemas Informáticos y Computación
Universidad Complutense de Madrid, Spain
{rafa,mario}@sip.ucm.es, cromdia@fdi.ucm.es

Abstract
Similarity-based Logic Programming (briefly, SLP ) has been proposed to enhance the LP paradigm with a kind of approximate reasoning which supports flexible information retrieval applications.
This approach uses a fuzzy similarity relation R between symbols in the program’s signature, while keeping the syntax for program clauses as in classical LP . Another recent proposal is the
QLP (D) scheme for Qualified Logic Programming, an extension
of the LP paradigm which supports approximate reasoning and
more. This approach uses annotated program clauses and a parametrically given domain D whose elements qualify logical assertions by measuring their closeness to various users’ expectations.
In this paper we propose a more expressive scheme SQLP (R, D)
which subsumes both SLP and QLP (D) as particular cases. We
also show that SQLP (R, D) programs can be transformed into semantically equivalent QLP (D) programs. As a consequence, existing QLP (D) implementations can be used to give efficient support for similarity-based reasoning.
Categories and Subject Descriptors D.1.6 [Programming Techniques]: Logic Programming; D.3.2 [Programming Languages]:
Language Classifications—Constraint and logic languages; F.3.2
[Theory of Computation]: Logics and Meanings of Programs—
Algebraic approaches to semantics
General Terms
Keywords

Algorithms, Languages, Theory

Qualification Domains, Similarity Relations

1. Introduction
The historical evolution of the research on uncertainty in Logic Programming (LP ) has been described in a recent recollection by V. S.
Subrahmanian [19]. Early approaches include the quantitative treatment of uncertainty in the spirit of fuzzy logic, as in van Emden’s
classical paper [20] and two subsequent papers by Subrahmanian
[17, 18]. The main contribution of [20] was a rigorous declarative
semantics for a LP language with program clauses of the form
A ← d − B, where the head A is an atom, the body B is a conjunction of atoms, and the so-called attenuation factor d ∈ (0, 1]
attached to the clause’s implication is used to propagate to the head

Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. To copy otherwise, to republish, to post on servers or to redistribute
to lists, requires prior specific permission and/or a fee.
PPDP’08, July 15–17, 2008, Valencia, Spain.
Copyright c 2008 ACM 978-1-60558-117-0/08/07. . . $5.00

the certainty factor d × b, where b is the minimum of the certainty
factors di ∈ (0, 1] previously computed for the various atoms occurring in the body. The papers [17, 18] proposed to use a special
lattice T in place of the lattice of the real numbers in the interval [0, 1] under their natural ordering. T includes two isomorphic
copies of [0, 1] whose elements are incomparable under T ’s ordering and can be used separately to represent degrees of truth and
falsity, respectively, thus enabling a simple treatment of negation.
Other main contributions of [17, 18] were the introduction of annotated program clauses and goals (later generalized to a much more
expressive framework in [7]), as well as goal solving procedures
more convenient and powerful than those given in [20].
A more recent line of research is Similarity-based Logic Programming (briefly, SLP ) as presented in [16] and previous related
works such as [3, 6, 5, 15]. This approach also uses the lattice [0, 1]
to deal with uncertainty in the spirit of fuzzy logic. In contrast to
approaches based on annotated clauses, programs in SLP are just
sets of definite Horn clauses as in classical LP . However, a similarity relation R (roughly, the fuzzy analog of an equivalence relation)
between predicate and function symbols is used to enable the unification terms that would be not unifiable in the classical sense, measured by some degree λ ∈ (0, 1]. There are different proposals for
the operational semantics of SLP programs. One possibility is to
apply classical SLD resolution w.r.t. a transformation of the original program [6, 15, 16]. Alternatively, a R-based SLD-resolution
procedure relying on R-unification can be applied w.r.t. to the original program, as proposed in [16]. Propositions 7.1 and 7.2 in [16]
state a correspondence between the answers computed by R-based
SLD resolution w.r.t. a given logic program P and the answers
computed by classical SLD resolution w.r.t. the two transformed
programs Hλ (P) (built by adding to P new clauses R-similar to
those in P up to the degree λ ∈ (0, 1]) and Pλ (built by replacing
all the function and predicate symbols in P by new symbols that
represent equivalence classes modulo R-similarity up to λ). The
SiLog system [8] has been developed to implement SLP and to
support applications related to flexible information retrieval from
the web.
The aim of the present paper is to show that similarity-based
reasoning can be expressed in QLP (D), a programming scheme
for Qualified LP over a parametrically given Qualification Domain
D recently presented in [14] as a generalization and improvement
of the classical approach by van Emden [20] to Quantitative
LP . Qualification domains are lattices satisfying certain natural
axioms. They include the lattice [0, 1] used both in [20] and in [16],
as well as other lattices whose elements can be used to qualify
logical assertions by measuring their closeness to different kinds
of users’ expectations. Programs in QLP (D) use D-attenuated
clauses of the form A ← d − B where A is an atom, B a finite
conjunction of atoms and d ∈ D \ {⊥} is the attenuation value

attached to the clause’s implication, used to propagate to the head
the qualification value d ◦ b, where b is the infimum in D of
the qualification values di ∈ D \ {⊥} previously computed for
the various atoms occurring in the body, and ◦ is an attenuation
operator coming with D. As reported in [14, 13], the classical
results in LP concerning the existence of least Herbrand models
of programs and the soundness and completeness of the SLD
resolution procedure (see e.g.[21, 2, 1]) have been extended to the
QLP (D) scheme, and potentially useful instances of the scheme
have been implemented on top of the Constraint Functional Logic
Programming (CF LP ) system T OY [4].
The results presented in this paper can be summarized as follows: we consider generalized similarity relations over a set S as
mappings R : S × S → D taking values in the carrier set D of an
arbitrarily given qualification domain D, and we extend QLP (D)
to a more expressive scheme SQLP (R, D) with two parameters for programming modulo R-similarity with D-attenuated Horn
clauses. We present a declarative semantics for SQLP (R, D) and
a program transformation mapping each SQLP (R, D) program P
into a QLP (D) program SR (P) whose least Herbrand model corresponds to that of P. Roughly, SR (P) is built adding to P new
clauses obtained from the original clauses in P by computing various new heads R-similar to a linearized version of the original
head, adding also R-similarity conditions Xi ∼ Xj to the body
and suitable clauses for the new predicate ∼ to emulate R-based
unification. Thanks to the SR (P) transformation, the sound and
complete procedure for solving goals in QLP (D) by D-qualified
SLD resolution and its implementation in the T OY system [14]
can be used to implement SQLP (R, D) computations, including
as a particular case SLP computations in the sense of [16].
Another recent proposal for reducing the SLP approach in [16]
to a fuzzy LP paradigm can be found in [11], a paper which relies
on the multi-adjoint framework for Logic Programming (MALP
for short) previously proposed in [9, 10]. MALP is a quite general framework supporting LP with weighted program rules over
different multi-adjoint lattices, each of which provides a particular choice of operators for implication, conjunction and aggregation of atoms in rule bodies. In comparison to the QLP (D)
scheme, the multi-adjoint framework differs in motivation and
scope. Multi-adjoint lattices and qualification domains are two different classes of algebraic structures. Concerning declarative and
operational semantics, there are also some significant differences
between QLP (D) and MALP. In particular, MALP ’s goal solving
procedure relies on a costly computation of reductant clauses, a
technique borrowed from [7] which can be avoided in QLP (D),
as discussed in the concluding section of [14].
In spite of these differences, the results in [11] concerning the
emulation of similarity-based can be compared to those in the
present paper. Theorem 24 in [11] shows that every classical logic
program P can be transformed into a MALP program PE,R which
can be executed using only syntactical unification and emulates the
successful computations of P using the SLD resolution with Rbased unification introduced in [16]. PE,R works over a particular
multi-adjoint lattice G with carrier set [0, 1] and implication and
conjunction operators chosen according to the so-called Gödel’s
semantics [22]. PE,R also introduces clauses for a binary predicate ∼ which emulates R-based unification, as in our transformation SR (P). Nevertheless, SR (P) is defined for a more general
class of programs and uses the R-similarity predicate ∼ only if
the source program P has some clause whose head is non-linear.
More detailed comparisons between the program transformations
SR (P), Hλ (P), Pλ and PE,R will be given in Subsection 4.2.
The rest of the paper is structured as follows: In Section 2 we
recall the qualification domains D first introduced in [14] and we
define similarity relations R over an arbitrary qualification domain.

In Section 3 we recall the scheme QLP (D) and we introduce its
extension SQLP (R, D) with its declarative semantics, given by
a logical calculus which characterizes the least Herbrand model
MP of each SQLP (R, D) program P. In Section 4 we define the
transformation SR (P) of any given SQLP (R, D) program P into
a QLP (D) program SR (P) such that MSR (P) = MP , we give
some comparisons to previously known program transformations,
and we illustrate the application of SR (P) to similarity-based
computation by means of a simple example. Finally, in Section 5
we summarize conclusions and comparisons to related work and
we point to planned lines of future work.

2. Qualification Domains and Similarity
Relations
2.1 Qualification Domains
Qualification Domains were introduced in [14] with the aim of
using their elements to qualify logical assertions in different ways.
In this subsection we recall their axiomatic definition and some
significant examples.
Definition 1. A Qualification Domain is any structure D = hD, ⊑,
⊥, ⊤, ◦i verifying the following requirements:
1. hD, ⊑, ⊥, ⊤i is a lattice with extreme points ⊥ and ⊤ w.r.t. the
partial ordering ⊑. For given elements d, e ∈ D, we write d ⊓ e
for the greatest lower bound (glb) of d and e and d ⊔ e for the
least upper bound (lub) of d and e. We also write d ⊏ e as
abbreviation for d ⊑ e ∧ d 6= e.
2. ◦ : D × D → D, called attenuation operation, verifies the
following axioms:
(a) ◦ is associative, commutative and monotonic w.r.t. ⊑.
(b) ∀d ∈ D : d ◦ ⊤ = d.
(c) ∀d ∈ D : d ◦ ⊥ = ⊥.
(d) ∀d, e ∈ D \ {⊥, ⊤} : d ◦ e ⊏ e.
(e) ∀d, e1 , e2 ∈ D : d ◦ (e1 ⊓ e2 ) = d ◦ e1 ⊓ d ◦ e2 .
In the rest of the paper, D will generally denote an arbitrary
qualification domain. For any
d finite S = {e1 , e2 , . . . , en } ⊆
D, the glb of S (noted as S) exists and can be computed as
e1 ⊓ e2 ⊓ · · · ⊓ en (which reduces to ⊤ in the case n = d
0). As
an easy consequence of the axioms, one gets the identity d ◦ S =
d
{d◦e | e ∈ S}. The QLP (D) scheme presented in [14] supports
LP over a parametrically given qualification domain D.
Example 1. Some examples of qualification domains are presented
below. Their intended use for qualifying logical assertions will
become more clear in Subsection 3.1.
1. B = ({0, 1}, ≤, 0, 1, ∧), where 0 and 1 stand for the two
classical truth values false and true, ≤ is the usual numerical
ordering over {0, 1}, and ∧ stands for the classical conjunction
operation over {0, 1}. Attaching 1 to an atomic formula A is
intended to qualify A as ‘true’ in the sense of classical LP .
2. U = (U, ≤, 0, 1, ×), where U = [0, 1] = {d ∈ R | 0 ≤
d ≤ 1}, ≤ is the usual numerical ordering, and × is the
multiplication operation. In this d
domain, the top element ⊤ is
1 and the greatest lower bound S of a finite S ⊆ U is the
minimum value min(S), which is 1 if S = ∅. Attaching an
element c ∈ U \ {0} to an atomic formula A is intended to
qualify A as ‘true with certainty degree c’ in the spirit of fuzzy
logic, as done in the classical paper [20] by van Emden. The
computation of qualifications c as certainty degrees in U is due
to the interpretation of ⊓ as min and ◦ as ×.
3. W = (P, ≥, ∞, 0, +), where P = [0, ∞] = {d ∈ R ∪ {∞} |
d ≥ 0}, ≥ is the reverse of the usual numerical ordering (with
∞ ≥ d for any d ∈ P), and + is the addition operation (with

∞ + d = d + ∞ = ∞ for any d ∈ P). In this
d domain, the
top element ⊤ is 0 and the greatest lower bound S of a finite
S ⊆ P is the maximum value max(S), which is 0 if S = ∅.
Attaching an element d ∈ P \ {∞} to an atomic formula A is
intended to qualify A as ‘true with weighted proof depth d’. The
computation of qualifications d as weighted proof depths in W
is due to the interpretation of ⊓ as max and ◦ as +.
4. Given 2 qualification domains Di = hDi , ⊑i , ⊥i , ⊤i , ◦i i (i ∈
{1, 2}), their cartesian product D1 × D2 is D =def hD, ⊑
, ⊥, ⊤, ◦i, where D =def D1 × D2 , the partial ordering ⊑
is defined as (d1 , d2 ) ⊑ (e1 , e2 ) ⇐⇒def d1 ⊑1 e1 and
d2 ⊑2 e2 , ⊥ =def (⊥1 , ⊥2 ), ⊤ =def (⊤1 , ⊤2 ), and the
attenuation operator ◦ is defined as (d1 , d2 ) ◦ (e1 , e2 ) =def
(d1 ◦1 e1 , d2 ◦2 e2 ). The product of two given qualification
domains is always another qualification domain, as proved
in [14]. Intuitively, each value (d1 , d2 ) belonging to D1 ×
D2 imposes the qualification d1 and also the qualification d2 .
For instance, values (c, d) belonging to U × W impose two
qualifications, namely: a certainty degree greater or equal than
c and a weighted proof depth less or equal than d.
For technical reasons that will become apparent in Section 4,
we consider the two structures U ′ resp. W ′ defined analogously
to U resp. W, except that ◦ behaves as min in U ′ and as max
in W ′ . Note that almost all the axioms for qualification domains
enumerated in Definition 1 hold in U ′ and W ′ , except that axiom
2.(d) holds only in the relaxed form ∀d, e ∈ D : d ◦ e ⊑
e. Therefore, we will refer to U ′ and W ′ as quasi qualification
domains.
2.2 Similarity relations
Similarity relations over a given set S have been defined in [16]
and related literature as mappings R : S × S → [0, 1] that satisfy
three axioms analogous to those required for classical equivalence
relations. Each value R(x, y) computed by a similarity relation R
is called the similarity degree between x and y. In this paper we
use a natural extension of the definition given in [16], allowing elements of an arbitrary qualification domain D to serve as similarity
degrees. As in [16], we are especially interested in similarity relations over sets S whose elements are variables and symbols of a
given signature.
Definition 2. Let a qualification domain D with carrier set D and
a set S be given.
1. A D-valued similarity relation over S is any mapping R :
S × S → D such that the three following axioms hold for
all x, y, z ∈ S:
(a) Reflexivity: R(x, x) = ⊤.
(b) Symmetry: R(x, y) = R(y, x).
(c) Transitivity: R(x, z) ⊒ R(x, y) ⊓ R(y, z).
2. The mapping R : S × S → D defined as R(x, x) = ⊤ for all
x ∈ D and R(x, y) = ⊥ for all x, y ∈ D, x 6= y is trivially a
D-valued similarity relation called the identity.
3. A D-valued similarity relation R over S is called admissible
iff S = Var ∪ CS ∪ P S (where the three mutually disjoint
sets Var, CS and P S stand for a countably infinite collection
of variables, a set of constructor symbols and a set of predicate
symbols, respectively) and the two following requirements are
satisfied:
(a) R restricted to Var behaves as the identity, i.e. R(X, X) =
⊤ for all X ∈ Var and R(X, Y ) = ⊥ for all X, Y ∈ Var,
X 6= Y .
(b) R(x, y) 6= ⊥ holds only if some of the following three
cases holds x, y: either x, y ∈ Var are both the same
variable; or else x, y ∈ CS are constructor symbols with

the same arity; or else x, y ∈ P S are predicate symbols
with the same arity.
The similarity degrees computed by a D-valued similarity relation must be interpreted w.r.t. the intended role of D-elements as
qualification values. For example, let R be an admissible similarity relation, and let c, d ∈ CS be two nullary constructor symbols
(i.e., constants). If R is U-valued, then R(c, d) can be interpreted
as a certainty degree for the assertion that c and d are similar. On
the other hand, if R is W-valued, then R(c, d) can be interpreted
as a cost to be paid for c to play the role of d. These two views are
coherent with the different interpretations of the operators ⊓ and ◦
in U and W, respectively.
In the rest of the paper we assume that any admissible similarity
relation R can be extended to act over terms, atoms and clauses.
The extension, also called R, can be recursively defined as in [16].
The following definition specifies the extension of R acting over
terms. The case of atoms and clauses is analogous.
Definition 3. (R acting over terms).
1. For X ∈ Var and for any term t different from X:
R(X, X) = ⊤ and R(X, t) = R(t, X) = ⊥.
2. For c, c′ ∈ CS with different arities n, m:
R(c(t1 , . . . , tn ), c′ (t′1 , . . . , t′m )) = ⊥.
3. For c, c′ ∈ CS with the same arity n:
R(c(t1 , . . . , tn ), c′ (t′1 , . . . , t′n )) = R(c, c′ )⊓R(t1 , t′1 )⊓. . .⊓
R(tn , t′n ).

3. Similarity-based Qualified Logic Programming
In this section we extend our previous scheme QLP (D) to a
more expressive scheme called Similarity-based Qualified Logic
Programming over (R, D) –abbreviated as SQLP (R, D)– which
supports both qualification over D in the sense of [14] and R-based
similarity in the sense of [16] and related research. Subsection 3.1
presents a quick review of the main results concerning syntax and
declarative semantics of QLP (D) already presented in [14], while
the extensions needed to conform the new SQLP (R, D) scheme
are presented in subsection 3.2.
3.1 Qualified Logic Programming
QLP (D) was proposed in our previous work [14] as a generic
scheme for qualified logic programming over a given qualification
domain D. In that scheme, a signature Σ providing constructor
and predicate symbols with given arities is assumed. Terms are
built from constructors and variables from a countably infinite set
Var (disjoint from Σ) and Atoms are of the form p(t1 , . . . , tn )
(shortened as p(tn ) or simply p(t)) where p is a n-ary predicate
symbol and ti are terms. We write AtΣ , called the open Herbrand
base, for the set of all atoms. A QLP (D) program P is a finite set
of D-qualified definite Horn clauses of the form A ← d− B where
A is an atom, B a finite conjunction of atoms and d ∈ D \ {⊥} is
the attenuation value attached to the clause’s implication.
As explained in [14], in our aim to work with qualifications we
are not only interested in just proving an atom, but in proving it
along with a qualification value. For this reason, D-qualified atoms
(A ♯ d where A is an atom and d ∈ D \ {⊥}) are introduced to
represent the statement that the atom A holds for at least the qualification value d. For use in goals to be solved, open D-annotated
atoms (A ♯ W where A is an atom and W a qualification variable
intended to take values over D) are also introduced, and a countably infinite set War of qualification variables (disjoint from Var
and Σ) is postulated. The annotated Herbrand base over D is defined as the set AtΣ (D) of all D-qualified atoms. A D-entailment
relation over AtΣ (D), defined as A ♯ d <D A′ ♯ d′ iff there is some
substitution θ such that A′ = Aθ and d′ ⊑ d, is used to for-

mally define an open Herbrand interpretation over D –from now
on just an interpretation– as any subset I ⊆ AtΣ (D) which is
closed under D-entailment. We write IntΣ (D) for the family of all
interpretations. The notion of model is such that given any clause
C ≡ A ← d−B1 , . . . , Bk in the QLP (D) program P, an interpretation I is said to be a model of C iff for any substitution θ and any
qualification values d1 , . . . , dk ∈ D \ {⊥}
d such that Bi θ ♯ di ∈ I
for all 1 ≤ i ≤ k, one has Aθ ♯ (d ◦ {d1 , . . . , dk }) ∈ I. The
interpretation I is also said to be a model of the QLP (D) program
P (written as I |= P) iff it happen to be a model of every clause in
P.
As technique to infer formulas (or in our case D-qualified
atoms) from a given QLP (D) program P, and following traditional ideas, we consider two alternative ways of formalizing an
inference step which goes from the body of a clause to its head:
both an interpretation transformer TP : IntΣ (D) → IntΣ (D),
and a qualified variant of Horn Logic, noted as QHL(D), called
Qualified Horn Logic over D. As both methods are equivalent and
correctly characterize the least Herbrand model of a given program
P, we will only be recalling the logic QHL(D), although we encourage the reader to see Section 3.2 in [14], where the fix-point
semantics is explained.
The logic QHL(D) is defined as a deductive system consisting
just of one inference rule: QMP(D), called Qualified Modus Ponens over D. Such rule allows us to give the following inference
step given that there were some (A ← d− B1 , . . . , Bk ) ∈ P, some
substitution θ such that A′ = Aθ and Bi′ = d
Bi θ for all 1 ≤ i ≤ k
and some d′ ∈ D \ {⊥} such that d′ ⊑ d ◦ {d1 , . . . , dk }:
B1′ ♯ d1

· · · Bk′ ♯ dk
A ′ ♯ d′

QMP(D)

Roughly, each QMP(D) inference step using an instance of a program clause A ← d−B has the effect of propagating to the head the
qualification value d ◦ b, where b is the infimum in D of the qualification values di ∈ D \ {⊥} previously computed for the various
atoms occurring in the body. This helps to understand the claims
made in Example 1 above about the intended use of elements of
the domains U and W for qualifying logical assertions. We use the
notations P ⊢QHL(D) A ♯ d (resp. P ⊢n
QHL(D) A ♯ d) to indicate
that A ♯ d can be inferred from the clauses in program P in finitely
many steps (resp. n steps). The least Herbrand model of P happens
to be MP = {A ♯ d | P ⊢QHL(D) A ♯ d}, as proved in [14].
3.2 Similarity-based Qualified Logic Programming
The scheme SQLP (R, D) presented in this subsection has two
parameters R and D, where D can be any qualification domain
and R can be any admissible D-valued similarity relation, in the
sense of Definition 2. The new scheme subsumes the approach in
[14] by behaving as QLP (D) in the case that R is chosen as the
identity, and it also subsumes similarity-based LP by behaving as
the approach in [16] and related papers in the case that D is chosen
as U.
Syntactically, SQLP (R, D) presents almost no changes w.r.t.
QLP (D), but the declarative semantics must be extended to account for the behavior of the parametrically given similarity relation R. As in the previous subsection, we assume a signature Σ providing again constructor and predicate symbols. Terms and Atoms
are built the same way they were in QLP (D), and AtΣ will stand
again for the set of all atoms, called the open Herbrand base. An
atom A is called linear if there is no variable with multiple occurrences in A; otherwise A is called non-linear. A SQLP (R, D)
program P is a finite set of D-qualified definite Horn clauses with
the same syntax as in QLP (D), along with a D-valued admissible
similarity relation R in the sense of Definition 2, item 2. Figure
1 shows a simple SQLP (R, U ) program built from the similarity

1
2
3

wild(lynx) <-0.9wild(boar) <-0.9wild(snake) <-1.0-

4
5

farm(cow) <-1.0farm(pig) <-1.0-

6
7

domestic(cat) <-0.8domestic(snake) <-0.4-

8
9

intelligent(A) <-0.9- domestic(A)
intelligent(lynx) <-0.7-

10
11

pacific(A) <-0.9- domestic(A)
pacific(A) <-0.7- farm(A)

12

pet(A) <-1.0- pacific(A), intelligent(A)
R(farm,domestic) = 0.3
R(pig,boar) = 0.7
R(lynx,cat) = 0.8

Figure 1. SQLP (R, U) program.
relation R given in the same figure and the qualification domain
U for certainty values. This program will be used just for illustrative purposes in the rest of the paper. The reader is referred to
Section 2 for other examples of qualification domains, and to the
references [8, 11] for suggestions concerning practical applications
of similarity-based LP .
D-qualified atoms (A ♯ d with A an atom and d ∈ D \ {⊥}) and
open D-annotated atoms (A ♯ W with A and atom and W ∈ W ar
a qualification variable intended to take values in D \{⊥}) will still
be used here. Similarly, the annotated open Herbrand base over D
is again defined as the set AtΣ (D) of all D-qualified atoms. At this
point, and before extending the notions of D-entailment relation
and interpretation to the SQLP (R, D) scheme, we need to define
what an R-instance of an atom is. Intuitively, when building Rinstances of an atom A, signature symbols occurring in A can be
replaced by similar ones, and different occurrences of the same
variable in A may be replaced by different terms, whose degree
of similarity must be taken into account. Technically, R-instances
of an atom A ∈ AtΣ are built from a linearized version of A
which has the form lin(A) = (Aℓ , Sℓ ) and is constructed as
follows: Aℓ is a linear atom built from A by replacing each n
additional occurrences of a variable X by new fresh variables Xi
(1 ≤ i ≤ n); and Sℓ is a set of similarity conditions X ∼ Xi
(with 1 ≤ i ≤ n) asserting the similarity of all variables in Aℓ that
correspond to the same variable X in A. As a concrete illustration,
let us show the linearization of two atoms. Note what happens when
the atom A is already linear as in the first case: Aℓ is just the same
as A and Sℓ is empty.
• H1 = p(c(X), Y )

lin(H1 ) = (p(c(X), Y ), {})
• H2 = p(c(X), X, Y )

lin(H2 ) = (p(c(X), X1 , Y ), {X ∼ X1 })
Now we are set to formally define the R-instances of an atom.
Definition 4. (R-instance of an atom). Assume an atom A ∈ AtΣ
and its linearized version lin(A) = (Aℓ , Sℓ ). Then, an atom A′ is

said to be an R-instance of A with similarity degree δ, noted as
(A′ , δ) ∈ [A]R , iff there are some atom AS anddsome substitution
θ such that A′ = AS θ and δ = R(Aℓ , AS ) ⊓ {R(Xi θ, Xj θ) |
(Xi ∼ Xj ) ∈ Sℓ } =
6 ⊥.
Next, the (R, D)-entailment relation over AtΣ (D) is defined
as follows: A ♯ d <(R,D) A′ ♯ d′ iff there is some similarity degree
δ such that (A′ , δ) ∈ [A]R and d′ ⊑ d ◦ δ. Finally, an open
Herbrand interpretation –just interpretation from now on– over
(R, D) is defined as any subset I ∈ AtΣ (D) which is closed
under (R, D)-entailment. That is, an interpretation I including a
given D-qualified atom A ♯ d is required to include all the ‘similar
instances’ A′ ♯ d′ such that A ♯ d <(R,D) A′ ♯ d′ , because we intend
to formalize a semantics in which all such similar instances are
valid whenever A ♯ d is valid. This complements the intuition given
for the D-entailment relation in QLP (D) to include the similar
instances (obtainable due to R) of each atom, and not only those
which are true because we can prove them for a better (i.e. higher in
D) qualification. Note that (R, D)-entailment is a refinement of Dentailment, since: A ♯ d <D A′ ♯ d′ =⇒ there is some substitution θ
such that A′ = Aθ and d′ ⊑ d =⇒ (A′ , ⊤) ∈ [A]R and d′ ⊑ d◦⊤
=⇒ A ♯ d <(R,D) A′ ♯ d′ .
As an example of the closure of interpretations w.r.t. (R, D)entailment, consider the U-qualified atom domestic(cat)#0.8.
As a trivial consequence of Proposition 2 below, this atom belongs
to the least Herbrand model of the program in Figure 1. On the
other hand, we also know that lynx is similar to cat with a similarity degree of 0.8 w.r.t. the similarity relation R in Figure 1.
Therefore, domestic(lynx) is a R-instance of domestic(cat)
to the degree 0.8. Then, by definition of (R, U)-entailment, it turns
out that domestic(cat)#0.8 <(R,U ) domestic(lynx)#0.64,
and the U-qualified atom domestic(lynx)#0.64 does also belong to the least model of the example program. Intuitively, 0.64 =
0.8 × 0.8 is the best U-qualification which can be inferred from the
U-qualification 0.8 for domestic(cat) and the R-similarity 0.8
between domestic(cat) and domestic(lynx).
We will write IntΣ (R, D) for the family of all interpretations
over (R, D), a family for which the following proposition can
be easily proved from the definition of an interpretation and the
definitions of the union and intersection of a family of sets.
Proposition 1. The family IntΣ (R, D) of all interpretations over
(R, D) is a complete lattice under the inclusion ordering ⊆, whose
extreme points are IntΣ (R, D) as maximum and ∅ as minimum.
Moreover, given anydfamily S
of interpretations I ⊆ IntΣ (R, D),
its
and glb are I = {I ∈ IntΣ (R, D) | I ∈ I} and
F lub T
I = {I ∈ IntΣ (R, D) | I ∈ I}, respectively.
Similarly as we did for the R-instances of an atom, we will define what the R-instances of a clause are. The following definition
tells us so.
Definition 5. (R-instance of a clause). Assume a clause C ≡
A ← d − B1 , . . . , Bk and the linearized version of its head
atom lin(A) = (Aℓ , Sℓ ). Then, a clause C ′ is said to be an Rinstance of C with similarity degree δ, noted as (C ′ , δ) ∈ [C]R ,
S
iff there are some atom
d A and some substitution θ such that
S
δ = R(Aℓ , A ) ⊓
{R(Xi θ, Xj θ) | (Xi ∼ Xj ) ∈ Sℓ } =
6 ⊥
and C ′ ≡ AS θ ← d− B1 θ, . . . , Bk θ.
Note that as an immediate consequence from Definitions 4 and 5
it is true that given two clauses C and C ′ such that (C ′ , δ) ∈ [C]R ,
and assuming A to be head atom of C and A′ to be the head atom
of C ′ , then we have that (A′ , δ) ∈ [A]R .
Let C be any clause A ← d−B1 , . . . , Bk in the program P, and
I ∈ IntΣ (R, D) any interpretation over (R, D). We say that I is a
model of C iff for any clause C ′ ≡ H ′ ← d−B1′ , . . . , Bk′ such that
(C ′ , δ) ∈ [C]R and any qualification values d1 , . . . , dk ∈ D \{⊥}

′
′
′
such that B
di ♯ di ∈ I for all 1 ≤ i ≤ k, one has H ♯ d ∈ I where
d′ = d ◦ {e, d1 , . . . , dk }. And we say that I is a model of the
SQLP (R, D) program P (also written I |= P) iff I is a model of
each clause in P.
We will provide now a way to perform an inference step from
the body of a clause to its head. As in the case of QLP (D),
this can be formalized in two alternative ways, namely an interpretation transformer and a variant of Horn Logic. Both approaches lead to equivalent characterizations of least program models. Here we focus on the second approach, defining what we
will call Similarity-based Qualified Horn Logic over (R, D) –
abbreviated as SQHL(R, D)–, another variant of Horn Logic and
an extension of the previous QHL(D). The logic SQHL(R, D)
is also defined as a deductive system consisting just of one inference rule SQM P (R, D), called Similarity-based Qualified Modus
Ponens over (R, D):
If ((A′ ← d − B1′ , . . . , Bk′ ), δ) ∈ [C]R for some clause C ∈
P with attenuation value d, then the followingdinference step is
allowed for any d′ ∈ D \{⊥} such that d′ ⊑ d◦ {δ, d1 , . . . , dk }:

B1′ ♯ d1

· · · Bk′ ♯ dk
A ′ ♯ d′

SQMP(R, D) .

We will use the notations P ⊢SQHL(R,D) A ♯ d (respectively
P ⊢n
SQHL(R,D) A ♯ d) to indicate that A ♯ d can be inferred from
the clauses in program P in finitely many steps (respectively n
steps). Note that SQHL(R, D) proofs can be naturally represented as upwards growing proof trees with D-qualified atoms at
their nodes, each node corresponding to one inference step having
the children nodes as premises.
The following proposition contains the main result concerning
the declarative semantics of the SQLP (R, D) scheme. A full
proof can be developed in analogy to the QLP (D) case presented
in [14, 13].
Proposition 2. Given any SQLP (R, D) program P. The least
Herbrand model (MP ) of P is
{A ♯ d | P ⊢SQHL(R,D) A ♯ d} .
The following example serves as an illustration of how the logic
SQHL(R, D) works over (R, U) using the example program
displayed in Figure 1.
Example 2. The following proof tree proves that the atom pet(lynx) can be inferred for at least a qualification value of 0.50 in the
SQLP (R, U) program P of Figure 1. Let’s see it:
(4)

domestic(lynx)#0.64
(2)
(3)
pacific(lynx)#0.57
intelligent(lynx)#0.70
(1)
pet(lynx)#0.50

where the clauses and qualification values used for each inference
step are:
(1) pet(lynx) <-1.0- pacific(lynx),intelligent(lynx)
is an instance of clause 12 in P and 0.50 ≤ 1.0 × min{1.0,
0.57, 0.70}. Note that the first 1.0 in the minimum is the one
which comes from the similarity relation as for this step we are
just using a plain instance of clause 12 in P.
(2) pacific(lynx) <-0.9- domestic(lynx) is a plain instance of clause 10 in P and 0.57 ≤ 0.9 × min{1.0, 0.64}.
(3) intelligent(lynx) <-0.7- is clause 9 in P and 0.70 ≤
0.70 × min{1.0}.
(4) The clause domestic(lynx) <-0.8- is an R-instance of
clause 6 with a similarity degree of 0.8 and we have 0.64 ≤
0.8 × min{0.8}.

4. Reducing Similarities to Qualifications
4.1 A Program Transformation
In this section we prove that any SQLP (R, D) program P can
be transformed into an equivalent QLP (D) program which will
be denoted by SR (P). The program transformation is defined as
follows:
Definition 6. Let P be a SQLP (R, D) program. We define the
transformed program SR (P) as:
SR (P) = PS ∪ P∼ ∪ Ppay
where the auxiliary sets of clauses PS , P∼ , Ppay are defined as:
• For each clause (H ← d− B) ∈ P and for each H ′ such that

R(Hℓ , H ′ ) 6= ⊥

(H ′ ← d− payR(Hℓ,H ′ ) , Sℓ , B) ∈ PS
where (Hℓ , Sℓ ) = lin(H).
• P∼ = {X ∼ X ← ⊤−} ∪ {(c(X n ) ∼ c′ (Y n ) ← ⊤ −

payR(c,c′ ) , X1 ∼ Y1 , . . . , Xn ∼ Yn ) | c, c′ ∈ CS of arity n,
R(c, c′ ) 6= ⊥}
• Ppay = {(payw ← w−) | for each atom payw occurring in
P∼ ∪ PS }

Note that the linearization of clause heads in this transformation
is motivated by the role of linearized atoms in the SQHL(R, D)
logic defined in Subsection 3.2 to specify the declarative semantics
of SQLP (R, D) programs. For instance, assume a SQLP (R, U )
program P including the clause p(X, X) ← 1.0− and two nullary
constructors c, d such that R(c, d) = 0.8. Then, SQHL(R, U)
supports the derivation P ⊢SQHL(R,U ) p(c, d) ♯ 0.8, and the transformed program SR (P) will include the clauses
p(X, X1 )
X∼X
c∼d
pay1.0
pay0.8

← 1.0− pay1.0 , X ∼ X1 ,
← 1.0−,
← 1.0− pay0.8 ,
← 1.0−,
← 0.8−

thus enabling the corresponding derivation SR (P) ⊢QHL(U )
p(c, d) ♯ 0.8 in QHL(U).
In general, P and SR (P) are semantically equivalent in the
sense that P ⊢SQHL(R,D) A ♯ d ⇐⇒ SR (P) ⊢QHL(D) A ♯ d
holds for any D-qualified atom A ♯ d, as stated in Theorem 1 below.
The next technical lemma will be useful for the proof of this
theorem.
Lemma 1. Let P be a SQLP (R, D) program and SR (P) its
transformed program according to Definition 6. Let t, s be two
terms in P’s signature and d ∈ D \ {⊥}. Then:
1. SR (P) ⊢QHL(D) (t ∼ s) ♯ d =⇒ d ⊑ R(t, s)
2. R(t, s) = d =⇒ SR (P) ⊢QHL(D) (t ∼ s) ♯ d
Proof. We prove the two items separately.
1. Let T be a QHL(D) proof tree witnessing
SR (P) ⊢QHL(D) (t ∼ s) ♯ d
We prove by induction on number of nodes of T that d ⊑
R(t, s). The basis case, with T consisting of just one node,
must correspond to some inference without premises, i.e., a
clause with empty body for ∼. Checking P∼ we observe that
X ∼ X ← ⊤− is the only possibility. In this case t and s
must be the same term and by the reflexivity of R (Def. 2),
R(t, s) = ⊤, which means d ⊑ R(t, s) for every d. In the
inductive step, we consider T with more than one node. Then

the inference step at the root of T uses some clause (c(X n ) ∼
′
c′ (X n ) ← ⊤− payR(c,c′ ) , X1 ∼ X1′ , . . . , Xn ∼ Xn′ ) ∈ P∼ ,
and must be of the form:
payw ♯ v (t1 ∼ s1 ) ♯ e1 . . . (tn ∼ sn ) ♯ en
c(tn ) ∼ c′ (sn ) ♯ d
where w = R(c, c′ ), v ∈ D, v ⊑ dw, t = c(tn ), s =
c′ (snd
), and e1 , . . . , en s.t. d ⊑ ⊤ ◦ {v, e1 , . . . , ek }, i.e.,
d ⊑ {v, e1 , . . . , ek }. By induction
hypothesis ei ⊑ R(ti , si )
d
for i = 1 . . . n. Then d ⊑ {v, e1 , . . . , en } implies d ⊑
d
{w, R(t1 , s1 ), . . . , R(tn , sn )} and hence d ⊑ R(t, s) (Def.
3, item 3).
2. If R(t, s) = d, d 6= ⊥, we prove that SR (P) ⊢QHL(D)
(t ∼ s) ♯ d by induction on the syntactic structure of t. The
basis corresponds to the case t = c for some constant c, or
t = Y for some variable Y . If t = c then s = c′ for some
other constant c′ . By Definition 6 there is a clause in P∼ of the
form (c ∼ c′ ← ⊤− payd ). Using this clause and the identity
substitution we can write the root inference step of a proof for
SR (P) ⊢QHL(D) (c ∼ c′ ) ♯ d as follows:
payd ♯ d
c ∼ c′ ♯ d
The condition required by
rule QMP(D) is in this
d the inferenced
particular case d ⊑ ⊤ ◦ {d}, and ⊤ ◦ {d} = d. Proving the
only premise payd ♯ d in QHL(D) is direct from its definition.
If t = Y , with Y a variable, then s = Y and d = ⊤ (otherwise
R(t, s) = ⊥). Then SR (P) ⊢QHL(D) (Y ∼ Y ) ♯ ⊤ can
be proved by using the clause (X ∼ X ←⊤−) ∈ P∼ with
substitution θ = {X 7→ Y }.
In the inductive step, t must be of the form c(tn ), with n ≥ 1,
and then s must be of the form c′ (sn ) (otherwise R(t, s) = ⊥).
From d = R(t, s) 6= ⊥ (hypotheses of the lemma) and
Definition 3 we have that R(c, c′ ) 6= ⊥. Then, by Definition
6, there is a clause in P∼ of the form:
c(X n ) ∼ c′ (Y n ) ← ⊤− payR(c,c′ ) , X1 ∼ Y1 , . . . , Xn ∼ Yn

By using the substitution θ = {X1 7→ t1 , . . . , Xn 7→
tn , Y1 7→ s1 , . . . , Yn 7→ sn } we can write the root inference
step in QHL(D) as:
payR(c,c′ ) ♯ R(c, c′ ) (ti ∼ si ♯ R(ti , si ))i=1...n
c(tn ) ∼ c′ (sn ) ♯ d
The inference can be applied because the condition
l
d ⊑ ⊤ ◦ {R(c, c′ ), R(t1 , s1 ), . . . , R(tn , sn )}
reduces to
d⊑

l
{R(c, c′ ), R(t1 , s1 ), . . . , R(tn , sn )}

which holds by Definition 3, item 3. Moreover, the premises
ti ∼ si ♯ R(ti , si ), i = 1 . . . n, hold in QHL(D) due to the
inductive hypotheses, and proving
payR(c,c′ ) ♯ R(c, c′ )
is straightforward from its definition.
Now we can prove the equivalence between semantic inferences
in QHL(D) w.r.t. P and semantic inferences in SQHL(R, D)
w.r.t. SR (P).
Theorem 1. Let P be a SQLP (R, D) program, A an atom in P’s
signature and d ∈ D \ {⊥}. Then:
P ⊢SQHL(R,D) A ♯ d ⇐⇒ SR (P) ⊢QHL(D) A ♯ d .

Proof. Let T be a SQHL(R, D) proof tree for some annotated
atom A ♯ d in P’s signature witnessing P ⊢SQHL(R,D) A ♯ d. We
prove that SR (P) ⊢QHL(D) A ♯ d by induction on the number of
nodes of T .
The inference step at the root of T must be of the form
B1′ ♯ d1

· · · Bk′ ♯ dk
A♯d

(1)

with ((A ← e − B1′ , . . . , Bk′ ), δ) ∈ [C]R for some clause
C ≡ (H ← e − B1 , . . . , Bk ) ∈ P (observe that the case
k = 0 corresponds to the induction basis). By Definition 5,
A = H ′ θ, Bi′ = Bi θ for d
some substitution θ and atom H ′
such that δ = R(Hℓ , H ′ ) ⊓ {R(Xi θ, Xj θ) | (Xi ∼ Xj ) ∈
Sℓ } 6= ⊥, with lin(H) = (Hℓ , Sℓ ). This means in particular that w = R(Hℓ , H ′ ) 6= ⊥, which by Definition 6 implies
that there is a clause C ′ in SR (P) of the form C ′ ≡ (H ′ ←
e − payw , Sℓ , B1 , . . . Bk ). Then the root inference step of the
deduction proving P ⊢QHL(D) A ♯ d will use the inference rule
QMP(D) with C ′ and substitution θ (such that H ′ θ = A) as follows:
payw θ ♯ w ((ui ∼ vi )θ ♯ ei )1≤i≤m B1′ ♯ d1 · · · Bk′ ♯ dk
(2)
A♯d
where Sℓ = {u1 ∼ v1 , . . . , um ∼ vm }, and ei = R(ui θ, vi θ) for
i = 1 . . . m.
Next we check that the premises can be proved from SR (P) in
QHL(D):
• payw θ = payw , since payw is a nullary predicate for every w.

Therefore SR (P) ⊢QHL(D) payw ♯ w is immediate from the
definition of payw in Definition 6.
• For each 1 ≤ i ≤ m, we observe that R(ui θ, vi θ) 6= ⊥
because δ 6= ⊥ has been computed above as the infimum
of a set including R(ui θ, vi θ) among its members. Then
SR (P) ⊢QHL(D) (ui ∼ vi )θ holds by Lemma 1, item 2.
• For each 1 ≤ i ≤ k, (1) shows that P ⊢SQHL(R,D) Bi′ ♯ di with
a proof tree having less nodes that T . Therefore, SR (P) ⊢QHL(D)
Bi′ ♯ di by induction hypothesis.
In order to perform the inference
d step (2), the QMP(D) inference rule also requires that d ⊑ e ◦ {w, e1 . . . , em , d1 , . . . , dk }.
This follows from the associativity of ⊓ since:
d
• As defined above, δ = R(Hℓ ,d
H ′) ⊓
{R(Xi θ, Xj θ) |
(Xi ∼ Xj ) ∈ Sℓ }, i.e. δ = w ⊓ {e1 . . . em }.
• By the SQMP(R, D) inference (1) we know that d ⊑ e ◦
d
{δ, d1 , . . . , dk }.
Let T be a QHL(D) proof tree witnessing SR (P) ⊢QHL(D)
A ♯ d for some atom A in P’s signature. We prove by induction on
the number of nodes of T that P ⊢SQHL(R,D) A ♯ d.
Since A is in P’s signature, the clause employed at the inference
step at the root of T must be in the set PS of Definition 6, and the
inference step at the root of T have of the form of the inference (2)
above. Hence this clause must have been constructed from a clause
C ≡ (H ← e − B1 , . . . , Bk ) ∈ P and some atom H ′ such that
A = H ′ θ and R(Hℓ , H ′ ) 6= ⊥, where lin(H) = (Hℓ , Sℓ ).
Then we can use C and θ to prove P ⊢SQHL(R,D) A ♯ d by a
SQMP(R, D) inference like (1) using the R-instance C ′ ≡ A ←
e−B1′ , . . . , Bk′ of C. The premises can be proved in SQHL(R, D)
by induction hypotheses, since all of them are also premises in
(2). Finally, we must check that the conditions required by (1)
hold:
(C ′ , δ) ∈ [C]R for some δ ∈ D,dδ 6= ⊥ s.t. d ⊑ e ◦
d
{δ, d1 , . . . , dk }. This is true for δ = {w, e′1 , . . . , e′n }, with
e′i = R(ui θ, vi θ) for i = 1 . . . m. Observe that in the premises of

(2) we have QHL(D) proofs of ui θ ∼ vi θ ♯ ei for i = 1 . . . m.
Therefore ei ⊑ e′i , by Lemma 1, item 1. Then
d
d ⊑ e ◦ d{w, e1 . . . , em , d1 , . . . , dk } (by(2))
⊑ e ◦ d{w, e′1 . . . , e′m , d1 , . . . , dk } (ei ⊑ e′i )
= e ◦ {δ, d1 , . . . , dk }
We must still prove that δ 6= ⊥. Observe that by the distributivity of ◦ w.r.t. ⊓ (Def. 1, axiom 2.(e)):
l
l
e ◦ {δ, d1 , . . . , dk } = (e ◦ δ) ⊓ (e ◦ {d1 , . . . , dk }) .
Therefore
d ⊑ (e ◦ δ) ⊓ (e ◦

l
{d1 , . . . , dk })

and from d 6= ⊥ we obtain (e ◦ δ) 6= ⊥ which implies δ 6= ⊥ due
to axiom 2.(c) in Definition 1. This completes the proof.
4.2

Comparison to Related Approaches

Other program transformations have been proposed in the literature with the aim of supporting R-based reasoning while avoiding
explicit R-based unification. Here we draw some comparisons between the program transformation SR (P) presented in the previous
subsection, the program transformations Hλ (P) and Pλ proposed
in [16], and the program transformation PE,R proposed in [11].
These three transformations are applied to a classical logic program
P w.r.t. a fuzzy similarity relation R over symbols in the program’s
signature. Both Hλ (P) and Pλ are classical logic programs to be
executed by SLD resolution, and their construction depends on a
fixed similarity degree λ ∈ (0, 1]. On the other hand, PE,R is a
multi-adjoint logic program over a particular multi-adjoint lattice
G, providing the uncertain truth values in the interval [0, 1] and two
operators for conjunction and disjunction in the sense of Gödel’s
fuzzy logic (see [22] for technical details). As in the case of our
own transformation SR (P), the construction of PE,R does not depend on any fixed similarity degree. The transformation SR (P)
proposed in this paper is more general in that it can be applied to
an arbitrary SQLP (R, D) program P, yielding a QLP (D) program SR (P) whose least Herbrand model is the same as that of
P.
We will restrict our comparisons to the case that P is chosen as
a similarity-based logic program in the sense of [16]. As an illustrative example, consider the simple logic program P consisting of
the following four clauses:
• Cr : r(X, Y ) ← p(X), q(Y ), s(X, Y )
• Cp : p(c(U )) ←
• Cq : q(d(V )) ←
• Cs : s(Z, Z) ←

Assume an admissible similarity relation defined by R(c, d) =
0.9 and consider the goal G : ← r(X, Y ) for P. Then, R-based
SLD-resolution as defined in [16] computes the answer substitution σ = {X 7→ c(U ), Y 7→ d(U )} with similarity degree 0.9.
This computation succeeds because R-based unification can compute the m.g.u. {Z 7→ c(U ), V 7→ U } with similarity degree 0.9
to unify the two atoms s(c(U ), d(V )) and s(Z, Z). Let us now examine the behavior of the the transformed programs H0.9 (P), P0.9 ,
SR (P) and PE,R and when working to emulate this computation
without explicit use of a R-based unification procedure.
1. H0.9 (P) is defined in [16] as the set of all clauses C ′ such that
R(C, C ′ ) ≥ 0.9 for some clause C ∈ P. In this case H0.9 (P)
includes the four clauses of P and the two additional clauses
p(d(U )) ← and q(c(V )) ←, derived by similarity from Cp
and Cq , respectively. Solving G w.r.t. H0.9 (P) by means of

classical SLD resolution produces two possible answer substitutions, namely σ1 = {X 7→ c(U ), Y 7→ c(U )} and
σ2 = {X 7→ d(U ), Y 7→ d(U )}. They are both similar to
σ to a degree greater or equal than 0.9, but none of them is
σ itself, contrary to the claim in Proposition 7.1 (i) from [16].
Therefore, this Proposition seems to hold only in a somewhat
weaker sense than the statement in [16]. This problem is due to
the possible non-linearity of a clause’s head, which is properly
taken into account by our transformation SR (P).
2. According to [16], P0.9 is computed from P by replacing all
the constructor and predicate symbols by new symbols that
represent the equivalence classes of the original ones modulo
R-similarity to a degree greater or equal than 0.9. In our example these classes are {r}, {p}, {q}, {s} and {c, d}, that
can be represented by the symbols r, p, q, s an e, respectively. Then, P0.9 replaces the two clauses Cp and Cq by
p(e(U )) ← and q(e(V )) ←, respectively, leaving the other
two clauses unchanged. Solving G w.r.t. P0.9 by means of
classical SLD resolution produces the answer substitution
σ ′ = {X 7→ e(U ), Y 7→ e(U )}, which corresponds to σ
modulo the replacement of the symbols in the original program
by their equivalence classes. This is consistent with the claims
in Proposition 7.2 from [16].
3. Note that P can be trivially converted into a semantically equivalent a SQLP (R, U) program, just by replacing each occurrence of the implication sign ← in P’s clauses by ← 1.0−. Then
SR (P) can be built as a QLP (U) program by the method explained in Subsection 4.1. It includes three clauses corresponding to Cr , Cp and Cq of P plus the following three new clauses:
• Cp′ : p(d(U )) ← 1.0− pay0.9
• Cq′ : q(c(V )) ← 1.0− pay0.9
• Cs′ : s(Z1 , Z2 ) ← 1.0− Z1 ∼ Z2

where Cp′ resp. Cq′ come from replacing the linear heads of Cp
resp. Cq by similar heads, and Cs comes from linearizing the
head of Cs , which allows no replacements by similarity. SR (P)
includes also the proper clauses for P∼ and Ppay , in particular
the following three ones:
• I : X ∼ X ← 1.0−
• S : c(X1 ) ∼ d(Y1 ) ← 1.0− pay0.9 , X1 ∼ Y1
• P : pay0.9 ← 0.9−

Solving goal G w.r.t. SR (P) by means of the U-qualified SLD
resolution procedure described in [14] can compute the answer
substitution σ with qualification degree 0.9. More precisely, the
initial goal can be stated as r(X, Y )#W 8 W ≥ 0.9, and
the computed answer is (σ, {W 7→ 0.9}). The computation
emulates R-based unification of s(c(U ), c(V )) and s(Z, Z)
to the similarity degree 0.9 by solving s(c(U ), c(V )) with the
clauses Cs′ , I, S and P .
4. The semantics of the MALP framework depending on the chosen multi-adjoint lattice is presented in [11]. A comparison with
the semantics of the QLP (D) scheme (see [14] and Subsection 3.1 above) shows that MALP programs over the multiadjoint lattice G behave as QLP (U ′ ) programs, where U ′ is
the quasi qualification domain analogous to U introduced at the
end of Subsection 2.1 above. For this reason, we can think of
the transformed program PE,R as presented with he syntax of a
QLP (U ′ ) program. The original program P can also be written
as a QLP (U ′ ) program just by replacing each the implication
sign ← occurring in P by ← 1.0−. As explained in [11], PE,R
is built by extending P with clauses for a new binary predicate
∼ intended to emulate the behaviour of R-based unification be-

tween terms. In our example, PE,R will include (among others)
the following clause for ∼:
• S ′ : c(X1 ) ∼ d(Y1 ) ← 0.9− X1 ∼ Y1

In comparison to the clause S in SR (P), clause S ′ needs no call
to a pay0.9 predicate at its body, because the similarity degree
0.9 = R(c, d) can be attached directly to the clause’s implication. This difference corresponds to the different interpretations
of ◦, which behaves as × in U and as min in U ′ .
Moreover, PE,R is defined to include a clause of the following
form for each pair of n-ary predicate symbols pd and pd′ such
that R(pd, pd′ ) 6= 0:
• Cpd,pd′ : pd(Y1 , . . . , Yn ) ← R(pd, pd′ )−

pd′ (X1 , . . . , Xn ), X1 ∼ Y1 , . . . , Xn ∼ Yn

In our simple example, all the clauses of this form correspond to
the trivial case where pd and pd′ are the same predicate symbol
and R(pd, pd′ ) = 1.0. Solving goal G w.r.t.SR (P) by means
of the procedural semantics described in Section 4 of [11] can
compute the answer substitution σ to the similarity degree 0.9.
More generally, Theorem 24 in [11] claims that for any choice
of P, PE,R can emulate any successful computation performed
by P using R-based SLD resolution.
In conclusion, the main difference between SR (P) and PE,R
pertains to the techniques used by both program transformations
in order to emulate the effect of replacing the head of a clause in
the original program by a similar one. PE,R always relies on the
clauses of the form Cpd,pd′ and the clauses for ∼, while SR (P) can
avoid to use the clauses for ∼ as long as all the clauses involved
in the computation have linear heads. In comparison to the two
transformations Hλ (P) and Pλ , our transformation SR (P) does
not depend on a fixed similarity degree λ and does not replace the
atoms in clause bodies by similar ones.

4.3 A Goal Solving Example
In order to illustrate the use of the transformed program SR (P)
for golving goals w.r.t. the original program P, we consider the
case where P is the SQLP (R, U ) program displayed in Figure 1.
The transformed program SR (P) obtained by applying Definition
6 is shown in Figure 2. The following observations are useful to
understand how the transformation has worked in this simple case:
• The value ⊤ in the domain U corresponds to the real number

1 and hence by reflexivity R(A, A) = 1 for any atom in the
signature of the program. Therefore, and as a consequence of
Definition 6, every clause in the original program gives rise to a
clause in the transformed program with the same head and with
the same body except for a new, first atom pay1.0 . For instance,
clauses 1, 2 and 3 in Figure 2 correspond to the same clause
numbers in Figure 1.
• Apart of the clauses corresponding directly to the original

clauses, the program of Figure 2 contains new clauses obtained by similarity with some clause heads in the original program. For instance, lines 4 and 5 are obtained by
similarity with clauses at lines 1 and 2 in the original program, respectively. The subindexes at literal pay correspond to
R(lynx, cat) = 0.8, R(boar, pig) = 0.7, respectively.
• Analogously, for instance the clause at line 10 (with head

farm(lynx)) is obtained by head-similarity with the clause of
line 6 in the SQLP (R, U ) program (head domestic(cat)),

from a given SQLP (R, D) program P to its transformed program
SR (P), because it was developed mainly for [14]. Therefore, the
transformed program shown in Figure 2 has been computed manually.
We will start running T OY and loading the QLP (U) instance
with the command /qlp(u):

1
2
3
4
5

wild(lynx) <-0.9- pay1.0
wild(boar) <-0.9- pay1.0
wild(snake) <-1.0- pay1.0
wild(cat) <-0.9- pay0.8
wild(pig) <-0.9- pay0.7

6
7
8
9
10
11

farm(cow) <-1.0- pay1.0
farm(pig) <-1.0- pay1.0
farm(boar) <-1.0- pay0.7
farm(cat) <-0.8- pay0.3
farm(lynx) <-0.8- pay0.3
farm(snake) <-0.4- pay0.3

12
13
14
15
16
17

domestic(cat) <-0.8- pay1.0
domestic(snake) <-0.4- pay1.0
domestic(lynx) <-0.8- pay0.8
domestic(cow) <-1.0- pay0.3
domestic(pig) <-1.0- pay0.3
domestic(boar) <-1.0- pay0.3

18
19
20

intelligent(A) <-0.9- pay1.0 ,domestic(A)
intelligent(lynx) <-0.7- pay1.0
intelligent(cat) <-0.7- pay0.8

21
22

pacific(A) <-0.9- pay1.0 ,domestic(A)
pacific(A) <-0.7- pay1.0 ,farm(A)

23

pet(A) <-1.0- pay1.0 ,pacific(A),intelligent(A)

24
25
26
27

pay1.0
pay0.8
pay0.7
pay0.3

Toy> /qlp(u)
this will have the effect of loading the Real Domain Constraints
library and the QLP (U) library into the system, the prompt
QLP(U)> will appear. Now we have to compile our example program (assume we have it in a text file called animals.qlp in
C:/examples/) with the command /qlptotoy (this command
will behave differently based on the actual instance loaded).
QLP(U)> /qlptotoy(c:/examples/animals)

QLP(U)> /qlpgoal(pet(A)#W | W>=0.50)
{ A -> cat,
W -> 0.5599999999999999 }
sol.1, more solutions (y/n/d/a) [y]?
{ A -> cat,
W -> 0.7200000000000001 }

Figure 2. Example of transformed program. (Note: no clauses for
∼ are needed because the original program was left-linear).
and the subindex at pay is obtained from
=
=
=

• There is no clause for predicate ∼ since all the heads in the

original program were already linear and therefore P∼ can be
left empty in practice.
• The clauses for pay correspond to the fragment Ppay in Defini-

tion 6.
In the rest of this subsection, we will show an execution for
the goal pet(A)#W | W >= 0.50 over the program SR (P) (see
Figure 2) with the aim of obtaining all those animals that could be
considered a pet for at least a qualification value of 0.50.
We are trying this execution in the prototype developed along
with [14] for the instances QLP (U) and QLP (W). Although this
prototype hasn’t been released as an integrated part of T OY, you
can download1 the prototype to try this execution. Please notice
that the prototype does not automatically do the translation process
1 Available

PROCESS COMPLETE
And finally we are set to launch our goal with the command
/qlpgoal. The solutions found for this program and goal are:

<-1.0<-0.8<-0.7<-0.3-

R(domestic(cat), farm(lynx))
R(domestic, farm) ⊓ R(cat, lynx)
0.3 ⊓ 0.8
0.3

Note that we didn’t write the extension of the file because it must
be .qlp. This will create the file animals.toy in the same directory as our former file. And this one will be an actual T OY program. We run the program with /run(c:/examples/animals)
(again without the extension –although this time we are assuming
.toy as extension–) and we should get the following message:

at: http://gpd.sip.ucm.es/cromdia/qlpd. There you
will also find specific instructions on how to install and run it as well as
text files with the program examples tried in here.

sol.2, more solutions (y/n/d/a) [y]?
{ A -> lynx,
W -> 0.5760000000000002 }
sol.3, more solutions (y/n/d/a) [y]?
{ A -> lynx,
W -> 0.5760000000000002 }
sol.4, more solutions (y/n/d/a) [y]?
no
At this point and if you remember the inference we did in
Example 2 for pet(lynx)#0.50, we have found a better solution (as you can see there are two solutions for lynx, and this is
due to the two different ways of proving intelligent(lynx):
intelligent(lynx)#0.7 using clause 19, and intelligent
(lynx)#0.576 using clauses 18 and 14.

5. Conclusions
Similarity-based LP has been proposed in [16] and related works
to enhance the LP paradigm with a kind of approximate reasoning which supports flexible information retrieval applications, as argued in [8, 11]. This approach keeps the syntax for program clauses
as in classical LP , and supports uncertain reasoning by using a
fuzzy similarity relation R between symbols in the program’s signature. We have shown that similarity-based LP as presented in
[16] can be reduced to Qualified LP in the QLP (D) scheme introduced in [14], which supports logic programming with attenuated program clauses over a parametrically given domain D whose

elements qualify logical assertions by measuring their closeness
to various users’ expectations. Using generalized similarity relations taking values in the carrier set of an arbitrarily given qualification domain D, we have extended QLP (D) to a more expressive scheme SQLP (R, D) with two parameters, for programming modulo R-similarity with D-attenuated Horn clauses. We
have presented a declarative semantics for SQLP (R, D) programs
and a semantics-preserving program transformation which embeds
SQLP (R, D) into QLP (D). As a consequence, the sound and
complete procedure for solving goals in QLP (D) by D-qualified
SLD resolution and its implementation in the T OY system [14]
can be used to implement SQLP (R, D) computations via the
transformation.
Our framework is quite general due to the availability of different qualification domains, while the similarity relations proposed
in [16] take fuzzy values in the interval [0, 1]. In comparison to
the multi-adjoint framework proposed in [11], the QLP (D) and
SQLP (R, D) schemes have a different motivation and scope, due
to the differences between multi-adjoint algebras and qualification
domains as algebraic structures. In contrast to the goal solving procedure used in the multi-adjoint framework, D-qualified SLD resolution does not rely on costly computations of reductant clauses
and has been efficiently implemented.
As future work, we plan to investigate an extension of the
R-based SLD resolution procedure proposed in [16] to be used
within the SQLP (R, D) scheme, and to develop an extension of
this scheme which supports lazy functional programming and constraint programming facilities. The idea of similarity-based unification has been already applied in [12] to obtain an extension of
needed narrowing, the main goal solving procedure of functional
logic languages. As in the case of [16], the similarity relations considered in [12] take fuzzy values in the real interval [0, 1].

Acknowledgments
The authors have been partially supported by the Spanish National
Projects MERIT-FORMS (TIN2005-09027-C03-03) and PROMESAS–CAM (S-0505/TIC/0407).

References
[1] K.R. Apt. Logic programming. In J. van Leeuwen, editor, Handbook
of Theoretical Computer Science, volume B: Formal Models and
Semantics, pages 493-574. Elsevier and The MIT Press, 1990.
[2] K.R. Apt and M.H. van Emden. Contributions to the theory of logic
programming. Journal of the Association for Computing Machinery
(JACM), 29(3):841-862, 1982.
[3] F. Arcelli and F. Formato. Likelog: A logic programming language for
flexible data retrieval. In Proceedings of the 1999 ACM Symposium
on Applied Computing (SAC’99), pages 260-267, New York, NY,
USA, 1999. ACM Press.

[6] G. Gerla and M.I. Sessa. Similarity in logic programming. In G.
Chen, M. Ying and K. Cai, editors, Fuzzy Logic and Soft Computing,
pages 19-31. Kluwer Academic Publishers, 1999.
[7] M. Kifer and V.S. Subrahmanian. Theory of generalized annotated
logic programs and their applications. Journal of Logic Programming,
12(3&4):335-367, 1992.
[8] V. Loia, S. Senatore and M.I. Sessa. Similarity-based SLD resolution
and its role for web knowledge discovery. Fuzzy Sets and Systems,
144(1):151-171, 2004.
[9] J. Medina, M. Ojeda-Aciego and P. Vojtáš. Multi-adjoint logic
programming with continuous semantics. In T. Eiter, W. Faber and
M. Truszczyinski, editors, Logic Programming and Non-Monotonic
Reasoning (LPNMR’01), volume 2173 of LNAI, pages 351-364.
Springer-Verlag, 2001.
[10] J. Medina, M. Ojeda-Aciego and P. Vojtáš. A procedural semantics
for multi-adjoint logic programming. In P. Brazdil and A. Jorge,
editors, Progress in Artificial Intelligence (EPIA’01), volume 2258 of
LNAI, pages 290-297. Springer-Verlag, 2001.
[11] J. Medina, M. Ojeda-Aciego and P. Vojtáš. Similarity-based
unification: A multi-adjoint approach. Fuzzy Sets and Systems,
146:43-62, 2004.
[12] G. Moreno and V. Pascual. Programming with fuzzy logic and
mathematical functions. In A.P.I. Bloch and A. Tettamanzi, editors,
Proceedings of the 6th International Workshop on Fuzzy Logic
and Applications (WILF’05), volume 3849 of LNAI, pages 89-98.
Springer-Verlag, 2006.
[13] M. Rodrı́guez-Artalejo and C.A. Romero-Dı́az. A generic scheme for
qualified logic programming (Technical Report SIC-1-08). Technical
Report, Universidad Complutense, Departamento de Sistemas
Informáticos y Computación, Madrid, Spain, 2008.
[14] M. Rodrı́guez-Artalejo and C.A. Romero-Dı́az. Quantitative logic
programming revisited. In J. Garrigue and M. Hermenegildo, editors,
Functional and Logic Programming (FLOPS’08), volume 4989 of
LNCS, pages 272-288. Springer-Verlag, 2008.
[15] M.I. Sessa. Translations and similarity-based logic programming.
Soft Computing, 5(2), 2001.
[16] M.I. Sessa. Approximate reasoning by similarity-based SLD
resolution. Theoretical Computer Science, 275(1&2):389-426, 2002.
[17] V.S. Subrahmanian. On the semantics of quantitative logic programs.
In Proceedings of the 4th IEEE Symposium on Logic Programming,
pages 173-182, San Francisco, 1987.
[18] V.S. Subrahmanian. Query processing in quantitative logic programming. In Proceedings of the 9th International Conference on
Automated Deduction, volume 310 of LNCS, pages 81-100, London,
UK, 1988. Springer-Verlag.
[19] V.S. Subrahmanian. Uncertainty in logic programming: Some
recollections. Association for Logic Programming Newsletter, 20(2),
2007.
[20] M.H. van Emden. Quantitative deduction and its fixpoint theory.
Journal of Logic Programming, 3(1):37-53, 1986.

[4] P. Arenas, A.J. Fernández, A. Gil, F.J. López-Fraguas, M. Rodrı́guezArtalejo and F. Sáenz-Pérez. T OY, a multiparadigm declarative
language. Version 2.3.1, 2007. R. Caballero and J. Sánchez (Eds.),
available at http://toy.sourceforge.net.

[21] M.H. van Emden and R.A. Kowalski. The semantics of predicate
logic as a programming language. Journal of the Association for
Computing Machinery (JACM), 23(4):733-742, 1976.

[5] F. Formato, G. Gerla and M.I. Sessa. Similarity-based unification.
Fundamenta Informaticae, 41(4):393-414, 2000.

[22] P. Vojtáš. Fuzzy logic programming. Fuzzy Sets and Systems,
124:361:370, 2001.

