arXiv:1009.1977v2 [cs.LO] 14 Jan 2011

Fixpoint & Proof-theoretic Semantics
for CLP with Qualification and Proximity ∗
Technical Report SIC-1-10
MARIO RODRÍGUEZ-ARTALEJO and CARLOS A. ROMERO-DÍAZ
Departamento de Sistemas Informáticos y Computación, Universidad Complutense
Facultad de Informática, 28040 Madrid, Spain
(e-mail: mario@sip.ucm.es, cromdia@fdi.ucm.es)

Abstract
Uncertainty in Logic Programming has been investigated during the last decades, dealing
with various extensions of the classical LP paradigm and different applications. Existing
proposals rely on different approaches, such as clause annotations based on uncertain truth
values, qualification values as a generalization of uncertain truth values, and unification
based on proximity relations. On the other hand, the CLP scheme has established itself as
a powerful extension of LP that supports efficient computation over specialized domains
while keeping a clean declarative semantics. In this report we propose a new scheme SQCLP designed as an extension of CLP that supports qualification values and proximity
relations. We show that several previous proposals can be viewed as particular cases of
the new scheme, obtained by partial instantiation. We present a declarative semantics for
SQCLP that is based on observables, providing fixpoint and proof-theoretical characterizations of least program models as well as an implementation-independent notion of goal
solutions.
KEYWORDS: Constraint Logic Programming, Qualification Domains and Values, Proximity Relations.

1 Introduction
Many extensions of logic programming (shortly LP) to deal with uncertainty have
been proposed in the last decades. A line of research not related to this report is
based on probabilistic extensions of LP such as (Ng and Subrahmanian 1992). Other
proposals in the field replace classical two-valued logic by some kind of many-valued
logic whose truth values can be attached to computed answers and are usually
interpreted as certainty degrees. The next paragraphs summarize some relevant
approaches of this kind.
There are extensions of LP using annotations in program clauses to compute a
certainty degree for the head atom from the certainty degrees previously computed
∗ This work has been partially supported by the Spanish projects STAMP (TIN2008-06622-C0301), PROMETIDOS–CM (S2009TIC-1465) and GPD–UCM (UCM–BSCH–GR58/08-910502).

2

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

for the body atoms. This line of research includes the seminal proposal of Quantitative Logic Programming by (van Emden 1986) and inspired later works such as the
Generalized Annotated logic Programs (shortly GAP) by (Kifer and Subrahmanian
1992) and the QLP scheme for Qualified LP (Rodrı́guez-Artalejo and Romero-Dı́az
2008b). While (van Emden 1986) and other early approaches used real numbers of
the interval [0, 1] as certainty degrees, QLP and GAP take elements from a parametrically given lattice to be used in annotations and attached to computed answers. In
the case of QLP, the lattice is called a qualification domain and its elements (called
qualification values) are not always understood as certainty degrees. As argued in
(Rodrı́guez-Artalejo and Romero-Dı́az 2008b), GAP is a more general framework,
but QLP’s semantics have some advantages for its intended scope.
There are also extended LP languages based on fuzzy logic (Zadeh 1965; Hájek
1998), which can be classified into two major lines. The first line includes Fuzzy LP
languages such as (Vojtáš 2001; Vaucheret et al. 2002; Guadarrama et al. 2004) and
the Multi-Adjoint LP (shortly MALP) framework by (Medina et al. 2001a; Medina
et al. 2001b). All these approaches extend classical LP by using clause annotations
and a fuzzy interpretation of the connectives and aggregation operators occurring
in program clauses and goals. There is a relationship between Fuzzy LP and GAP
that has been investigated in (Krajči et al. 2004). Intended applications of Fuzzy
LP languages include expert knowledge representation.
The second line includes Similarity-based LP (shortly SLP) in the sense of (Arcelli
and Formato 1999; Sessa 2002; Loia et al. 2004) and related proposals, which keep
the classical syntax of LP clauses but use a similarity relation over a set of symbols
S to allow “flexible” unification of syntactically different symbols with a certain
approximation degree. Similarity relations over a given set S have been defined in
(Zadeh 1971; Sessa 2002) and related literature as fuzzy relations represented by
mappings S : S × S → [0, 1] which satisfy reflexivity, symmetry and transitivity
axioms analogous to those required for classical equivalence relations. A more general notion called proximity relation was introduced in (Dubois and Prade 1980) by
omitting the transitivity axiom. As noted by (Shenoi and Melton 1999) and other
authors, the transitivity property required for similarity relations may conflict with
user’s intentions in some cases. The Bousi∼Prolog language (Julián-Iranzo et al.
2009; Julián-Iranzo and Rubio-Manzano 2009b; Julián-Iranzo and Rubio-Manzano
2009a) has been designed with the aim of generalizing SLP to work with proximity relations. A different generalization of SLP is the SQLP scheme (Caballero
et al. 2008), designed as an extension of the QLP scheme. In addition to clause
annotations in QLP style, SQLP uses a given similarity relation S : S × S → D
(where D is the carrier set of a parametrically given qualification domain) in order
to support flexible unification. In the sequel we use the acronym SLP as including
proximity-based LP languages also. Intended applications of SLP include flexible
query answering. An analogy of proximity relations in a different context (namely
partial constraint satisfaction) can be found in (Freuder and Wallace 1992), where
several metrics are proposed to measure the proximity between the solution sets of
two different constraint satisfaction problems.
Several of the above mentioned LP extensions (including GAP, QLP, the Fuzzy

Fixpoint & Proof-theoretic Semantics for SQCLP

3

LP language in (Guadarrama et al. 2004) and SQLP) have used constraint solving
as an implementation technique. However, we only know two approaches which
have been conceived as extensions of the classical CLP scheme (Jaffar and Lassez
1987). Firstly, (Riezler 1996; Riezler 1998) extended the formulation of CLP by
(Höhfeld and Smolka 1988) with quantitative LP in the sense of (van Emden 1986);
this work was motivated by problems from the field of natural language processing.
Secondly, (Bistarelli et al. 2001) proposed a semiring-based approach to CLP, where
constraints are solved in a soft way with levels of consistency represented by values
of a semiring. This approach was motivated by constraint satisfaction problems
and implemented with clp(FD,S) in (Georget and Codognet 1998) for a particular
class of semirings which enable to use local consistency algorithms. The relationship
between (Riezler 1996; Riezler 1998; Bistarelli et al. 2001) and the results of this
report will be further discussed in Section 4.
Finally, there are a few preliminary attempts to combine some of the above mentioned approaches with the Functional Logic Programming (shortly FLP) paradigm
found in languages such as Curry (Hanus ) and T OY (Arenas et al. 2007). Similaritybased unification for FLP languages has been investigated by (Moreno and Pascual
2007), while (Caballero et al. 2009) have proposed a generic scheme QCFLP designed as a common extension of the two schemes CLP and QLP with first-order
FLP features.
In this report we propose a new extension of CLP that supports qualification
values and proximity relations. More precisely, we define a generic scheme SQCLP
whose instances SQCLP(S, D, C) are parameterized by a proximity relation S, a
qualification domain D and a constraint domain C. We will show that several previous proposals can be viewed as particular cases of SQCLP, obtained by partial
instantiation. Moreover, we will present a declarative semantics for SQCLP that is
inspired in the observable CLP semantics by (Gabbrielli and Levi 1991; Gabbrielli
et al. 1995) and provides fixpoint and proof-theoretical characterizations of least
program models as well as an implementation-independent notion of goal solution
that can be used to specify the expected behavior of goal solving systems.
The reader is assumed to be familiar with the semantic foundations of LP (Lloyd
1987; Apt 1990) and CLP (Jaffar and Lassez 1987; Jaffar et al. 1998). The rest of
the report is structured as follows: Section 2 introduces constraint domains, qualification domains and proximity relations. Section 3 presents the SQCLP scheme and
the main results on its declarative semantics. Finally, Section 4 concludes by giving
an overview of related approaches (many of which can be viewed as particular cases
of SQCLP) and pointing to some lines open for future work.

2 Constraints, Qualification & Proximity
2.1 Constraint Domains
The Constraint Logic Programming paradigm (CLP) was introduced in (Jaffar and
Lassez 1987) with the aim of generalizing the Herbrand Universe which underlies
classical Logic Programming (LP) to other domains tailored to specific applica-

4

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

tion areas. In this seminal paper, CLP was introduced as a generic scheme with
instances CLP(C) parameterized by constraint domains C, each of which supplies
several items: a constraint language providing a class of domain specific formulae, called constraints and serving as logical conditions in CLP(C) programs and
computations; a constraint structure serving as interpretation of the constraint language; a constraint theory serving as a basis for proof-theoretical deduction with
constraints; and a constraint solver for checking constraint satisfiability. Certain
assumptions were made to ensure the proper relationship between the constraint
language, structure, theory and solver, so that the classical results on the operational and declarative semantics of LP (Lloyd 1987; Apt 1990) could be extended to
all the CLP(C) languages. A revised and updated presentation of the main results
from (Jaffar and Lassez 1987) can be found in (Jaffar et al. 1998), while a survey
of CLP as a programming paradigm is given in (Jaffar and Maher 1994).
The notion of constraint domain is a key ingredient of the CLP scheme. In addition to the classical formulation in (Jaffar and Lassez 1987; Jaffar et al. 1998), other
formalizations have been used for different purposes. Some significative examples
are: the CLP scheme proposed in (Höhfeld and Smolka 1988), motivated by applications to computational linguistics and allowing more than one constraint structure
to come along with a given constraint language; the proof-theoretical notion of
constraint system given in (Saraswat 1992), intended for application to concurrent
constraint languages; and the constraint systems proposed in (Lucio et al. 2008) as
the basis of a functorial semantics for CLP with negation, where a single constraint
structure is replaced by a class of elementary equivalent structures.
In this paper we will use a simple notion of constraint domain, motivated by three
main considerations: firstly, to focus on declarative semantics, rather than prooftheoretic or operational issues; secondly, to provide a purely relational framework;
and thirdly, to clarify the interplay between domain-specific programming resources
such as basic values and primitive predicates, and general-purpose programming
resources such as data constructors and defined predicates.

2.1.1 Preliminary notions
Before presenting constraint domains in a formal way, let us introduce some mainly
syntactic notions that will be used all along the paper.
Definition 2.1 (Signatures)
We assume a universal programming signature Γ = hDC, DP i where DC =
S
S
n
and DP = n∈N DP n are infinite and mutually disjoint sets of free
n∈N DC
function symbols (called data constructors in the sequel) and defined predicate
symbols, respectively, ranked by arities. We will use domain specific signatures
S
Σ = hDC, DP, P P i extending Γ with a disjoint set P P = n∈N P P n of primitive
predicate symbols, also ranked by arities. The idea is that primitive predicates come
along with constraint domains, while defined predicates are specified in user programs. Each P P n maybe any countable set of n-ary predicate symbols. In practice,
P P is expected to be a finite set.

Fixpoint & Proof-theoretic Semantics for SQCLP

5

In the sequel, we assume that any signature Σ includes two nullary constructors
true, false ∈ DC 0 to represent the boolean values, a binary constructor pair ∈
DC 2 to represent ordered pairs, as well as constructors to represent lists and other
common data structures. Given a signature Σ, a set B of basic values u and a
countably infinite set Var of variables X, terms and atoms are built as defined
below, where on abbreviates the n-tuple of syntactic objects o1 , . . . , on and var(o)
denotes the set of all variables occurring in the syntactic object o.
Definition 2.2 (Terms and atoms)
• Constructor Terms t ∈ Term(Σ, B, Var) have the syntax t ::= X|u|c(tn ),
where c ∈ DC n . They will be called just terms in the sequel. In concrete
examples, we will use Prolog syntax for terms built with list constructors,
and we will write (t1 , t2 ) rather than pair(t1 , t2 ) for terms representing ordered
pairs.
• The set of all the variables occurring in t is noted as var(t). A term t is called
ground iff var(t) = ∅. Term(Σ, B) stands for the set of all ground terms.
• Atoms A ∈ At(Σ, B, Var) can be defined atoms r(tn ), where r ∈ DP n and
ti ∈ Term(Σ, B, Var) (1 ≤ i ≤ n); primitive atoms p(tn ), where p ∈ P P n
and ti ∈ Term(Σ, B, Var) (1 ≤ i ≤ n); and equations t1 == t2 , where t1 , t2 ∈
Term(Σ, B, Var) and ‘==’ is the equality symbol, which does not belong to the
signature Σ. Primitive atoms are noted as κ and the set of all primitive atoms
is noted PAt(Σ, B, Var). Equations and primitive atoms are collectivelly called
C-based atoms.
• The set of all the variables occurring in A is noted as var(A). An atom A
is called ground iff var(A) = ∅. The set of all ground atoms (resp. ground
primitive atoms) is noted as GAt(Σ, B) (resp. GPAt(Σ, B)).
Note that the equality symbol ‘==’ used as part of the syntax of equational
atoms is not the same as the symbol ‘=’ generally used for mathematical equality.
In particular, metalevel equations o = o0 can be used to assert the identity of two
syntactical objects o and o0 .
Following well-known ideas, the syntactical structure of terms and atoms can be
represented by means of trees with nodes labeled by signature symbols, basic values
and variables. In the sequel we will use the notation ktk to denote the syntactical size
of t measured as the number of nodes in the tree representation of t. The positions
of nodes in this tree can be noted as finite sequences p of natural numbers. In
particular, the empty sequence ε represents the root position. The next definition
presents essential notions concerning positions in terms. Positions in atoms can be
treated similarly.
Definition 2.3 (Positions)
1. The set pos(t) of positions of the term t is defined by recursion on the structure
of t:
• pos(X) = {ε} for each variable X ∈ Var.
• pos(u) = {ε} for each basic value u ∈ B.
Sn
• pos(c(tn )) = {ε} ∪ i=1 {iq | q ∈ pos(ti )} for each c ∈ DC n .

6

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az
2. Given p ∈ pos(t), the symbol t ◦ p of t at position p is defined recursively:
•
•
•
•

X ◦ ε = X for each variable X ∈ Var.
u ◦ ε = u for each basic value u ∈ B.
c(t1 , . . . , tn ) ◦ ε = c if c ∈ DC n .
c(t1 , . . . , tn ) ◦ iq = ti ◦ q if c ∈ DC n , 1 ≤ i ≤ n and q ∈ vpos(ti ).

3. Given p ∈ pos(t), the subterm t|p of t at position p is defined as follows:
• t|ε = t for any t.
• c(t1 , . . . , tn )|iq = ti |q if c ∈ DC n , 1 ≤ i ≤ n and q ∈ pos(ti ).
4. p ∈ pos(t) is called a variable position of t iff t|p is a variable, and a rigid position of t otherwise. We define vpos(t) = {p ∈ pos(t) | p is a variable position}
and rpos(t) = {p ∈ pos(t) | p is a rigid position}.
5. Given p ∈ vpos(t) and another term s, the result of replacing s for the subterm
of t at position p is noted as t[s]p . See e.g. (Baader and Nipkow 1998) for a
recursive definition.
As usual, substitutions are defined as mappings σ : Var → Term(Σ, B, Var) assigning terms to variables. The set of all substitutions is noted as Subst(Σ, B, Var).
Substitutions are extended to act over terms and other syntactic objects o in the
natural way. By convention, the result of replacing each variable X occurring in o
by σ(X) is noted as oσ. Other common notions concerning substitutions are defined
as follows:
Definition 2.4 (Notions concerning Substitutions)
• The composition σσ 0 of two substitutions is such that o(σσ 0 ) equals (oσ)σ 0 .
• For a given σ ∈ Subst(Σ, B, Var), the domain dom(σ) is defined as {X ∈ Var |
S
Xσ 6= X}, and the variable range vran(σ) is defined as X∈dom(σ) var(Xσ).
• A substitution σ is called ground iff Xσ is a ground term for all X ∈ dom(σ).
The set of all ground substitutions is noted GSubst(Σ, B).
• A substitution σ is called finite iff dom(σ) is a finite set, say {X1 , . . . , Xk }. In
this case, σ can be represented as the set of bindings {X1 7→ t1 , . . . , Xk 7→ tk },
where ti = Xi σ for all 1 ≤ i ≤ k.
• Assume two substitutions σ, σ 0 , a set of variables X and a variable Y . The
notation σ =X σ 0 means that Xσ = Xσ 0 holds for all variables X ∈ X . We
also write σ =\X σ 0 and σ =\Y σ 0 to abbreviate σ =Var\X σ 0 and σ =Var\{Y }
σ 0 , respectively.
2.1.2 Constraint domains, constraints and their solutions
We are now prepared to present constraint domains as mathematical structures
providing a set of basic values along with an terms and an interpretation of primitive
predicates1 . The formal definition is as follows:
1

As we will see in Section 3, the interpretation of defined predicate symbols is program dependent.

Fixpoint & Proof-theoretic Semantics for SQCLP

7

Definition 2.5 (Constraint Domains)
A Constraint Domain of signature Σ is any relational structure of the form C =
hC, {pC | p ∈ P P }i such that:
1. The carrier set C is Term(Σ, B) for a certain set B of basic values. When
convenient, we note B and C as BC and CC , respectively.
2. pC : C n → {0, 1}, written simply as pC ∈ {0, 1} in the case n = 0, is called
the interpretation of p in C. A ground primitive atom p(tn ) is true in C iff
pC (tn ) = 1; otherwise p(tn ) is false in C.
For the examples in this paper we will use a constraint domain R which allows to
work with arithmetic constraints over the real numbers, as formalized in Definition
2.6 below.
Definition 2.6 (The Real Constraint Domain R)
The constraint domain R is defined to include:
• The set of basic values BR = R. Note that CR includes ground terms built
from real values and data constructors, in addition to real numbers.
• Primitive predicates for encoding the usual arithmetic operations over R. For
instance, the addition operation + over R is encoded by a ternary primitive
predicate op+ such that, for any t1 , t2 ∈ CR , op+ (t1 , t2 , t) is true in R iff
t1 , t2 , t ∈ R and t1 + t2 = t. In particular, op+ (t1 , t2 , t) is false in R if either
t1 or t2 includes data constructors. The primitive predicates encoding other
arithmetic operations such as × and − are defined analogously.
• Primitive predicates for encoding the usual inequality relations over R. For
instance, the ordering ≤ over R is encoded by a binary primitive predicate
cp≤ such that, for any t1 , t2 ∈ CR , cp≤ (t1 , t2 ) is true in R iff t1 , t2 , t ∈ R and
t1 ≤ t2 . In particular, cp≤ (t1 , t2 ) is false in R if either t1 or t2 includes data
constructors. The primitive predicates encoding the other inequality relations,
namely >, ≥ and >, are defined analogously.
The domain R is well known as the basis of the CLP(R) language and system
(Jaffar et al. 1992). Some presentations of R known in the literature represent the
arithmetical operations by using primitive functions instead of primitive predicates.
In this paper we have chosen to work in a purely relational framework in order to
simplify some technicalities without loss of real expressivity.
Other useful instances of constraint domains are known in the Constraint Programming literature; see e.g. (Jaffar and Maher 1994; López-Fraguas et al. 2007).
In particular, the Herbrand domain H is intended to work just with equality constraints, while FD allows to work with constraints involving finite domain variables.
The set of basic values of FD is Z. There are also known techniques for combining
several given constraint domains into a more expressive one; see e.g. the coordination domains defined in (Estévez-Martı́n et al. 2009).
The following definition introduces constraints over a given domain:

8

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

Definition 2.7 (Constraints and Their Solutions)
Given a constraint domain C of signature Σ:
1. Atomic constraints over C are of two kinds: primitive atoms p(tn ) and equations t1 == t2 .
2. Compound constraints are built from atomic constraints using logical conjunction ∧, existential quantification ∃, and sometimes other logical operations.
Constraints of the form ∃X1 . . . ∃Xn (B1 ∧ . . . ∧ Bm ) –where Bj (1 ≤ j ≤ m)
are atomic– are called existential. The set of all constraints over C is noted
ConC .
3. Substitutions σ : Var → Term(Σ, B, Var) where Term(Σ, B, Var) is built using
the set BC of basic values are called C-substitutions. Ground substitutions η ∈
GSubst(Σ, B) are called variable valuations. The set of all possible variable
valuations is noted ValC .
4. The solution set SolC (π) of a constraint π ∈ ConC is defined by recursion on
π’s syntactic structure as follows:
• If π is a primitive atom p(tn ), then SolC (π) is the set of all η ∈ ValC
such that p(tn )η is ground and true in C.
• If π is an equation t1 == t2 , then SolC (π) is the set of all η ∈ ValC such
that t1 η and t2 η are ground and syntactically identical terms.
• If π is π1 ∧ π2 then SolC (π) = SolC (π1 ) ∩ SolC (π2 ).
• If π is ∃Xπ 0 then SolC (π) is the set of all η ∈ ValC such that η 0 ∈ SolC (π 0 )
holds for some η 0 ∈ ValC verifying η =\X η 0 .
π is called satisfiable over C iff SolC (π) 6= ∅, and π is called unsatisfiable over
C iff SolC (π) = ∅.
T
5. The solution set SolC (Π) of a set Π of constraints is defined as π∈Π SolC (π).
In this way, finite sets of constraints are interpreted as the conjunction of
their members. Π is called satisfiable over C iff SolC (Π) 6= ∅, and Π is called
unsatisfiable over C iff SolC (Π) = ∅.
6. A constraint π is entailed by a set of constraints Π (in symbols, Π |=C π) iff
SolC (Π) ⊆ SolC (π).
The following example illustrates the previous definition:
Example 2.1 (Constraint solutions and constraint entailment over R)
Consider the set of constraints Π = {cp≥ (A, 3.0), op+ (A, A, X), op× (2.0, A, Y )} ⊆
ConR . Then:
1. For any valuation η ∈ ValR : η ∈ SolR (Π) holds iff η(A), η(X) and η(Y ) are
real numbers a, x, y ∈ R such that a ≥ 3.0, a + a = x and 2.0 × a = y.
2. Due to the previous item, the following R-entailments are valid:
(a) Π |=R cp> (X, 5.5), because SolR (Π) ⊆ SolR (cp> (X, 5.5)).
(b) Π |=R X == Y , because SolR (Π) ⊆ SolR (X == Y).
(c) Π |=R c(X) == c(Y ), because SolR (Π) ⊆ SolR (c(X) == c(Y)).
Here we assume c ∈ DC 1 .

Fixpoint & Proof-theoretic Semantics for SQCLP

9

(d) Π |=R [X, Y ] == [Y, X], because SolR (Π) ⊆ SolR ([X,Y] ==
[Y,X]). Here, the terms [X, Y ] and [Y, X] are built from variables
and list constructors.
The next technical result will be useful later on:
Lemma 2.1 (Substitution Lemma)
Assume a set of constraints Π ⊆ ConC and a C-substitution σ. Then:
1. For any valuation η ∈ ValC : η ∈ SolC (Πσ) ⇐⇒ ση ∈ SolC (Π).
2. For any constraint π ∈ ConC : Π |=C π =⇒ Πσ |=C πσ.
Proof
Let us give a separate reasoning for each item.
1. The following statement holds for any constraint π ∈ ConC :
(?) η ∈ SolC (πσ) ⇐⇒ ση ∈ SolC (π)
In fact, (?) can can be easily proved reasoning by induction on the syntactic structure of π. Now, using (?) we can reason as follows:
η ∈ SolC (Πσ) ⇐⇒ η ∈ SolC (πσ) for all π ∈ Π ⇐⇒(?)
ση ∈ SolC (π) for all π ∈ Π ⇐⇒ ση ∈ SolC (Π)
2. Assume Π |=C π. For the sake of proving Πσ |=C πσ, also assume an arbitrary
η ∈ SolC (Πσ). Then we get ση ∈ SolC (Π) because of item 1 and ση ∈ SolC (π) due
to the assumption Π |=C π, which implies η ∈ SolC (πσ) again because of item 1.
Since η is arbitrary, we have proved SolC (Πσ) ⊆ SolC (πσ), i.e. Πσ |=C πσ.
2.1.3 Term equivalence w.r.t. a given constraint set
Given two terms t, s we will use the notation t ≈Π s (read as t and s are Πequivalent) as an abbreviation of Π |=C t == s, assuming that the constraint domain
C and the constraint set Π ⊆ ConC are known. For the sake of simplicity, C is not
made explicit in the ≈Π notation. In this subsection we present some properties
related to ≈Π which will be needed later. First, we prove that ≈Π is an equivalence
relation with a natural characterization.
Lemma 2.2 (Π-Equivalence Lemma)
1. ≈Π is an equivalence relation over Term(Σ, B, Var).
2. For any given terms t and s the following two statements are equivalent:
(a) t ≈Π s.
(b) For any common position p ∈ pos(t) ∩ pos(s) some of the cases
below holds:
i t ◦ p or s ◦ p is a variable, and moreover t|p ≈Π s|p .
ii t ◦ p = s ◦ p = u for some u ∈ BC .
iii t ◦ p = s ◦ p = c for some n ∈ N and some c ∈ DC n .
3. ≈Π boils down to the syntactic equality relation = when Π is the empty set.

10

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

Proof
We give a separate reasoning for each item.
1. Checking that ≈Π satisfies the axioms of an equivalence relation (i.e. reflexivity,
symmetry and transitivity) is quite obvious.
2. Due to Definition 2.7, t ≈Π s holds iff tη and sη are identical ground terms for each
η ∈ SolC (Π). This statement can be proved equivalent to condition 2.(b) reasoning
by induction on ktk + ksk.
3. Note that t ≈∅ s holds iff tη and sη are identical ground terms for each η ∈ SolC (∅) =
ValC . This can happen iff t and s are syntactically identical.
Since the set Var of all variables is countably infinite, we can assume an arbitrarily
fixed bijective mapping ord : Var → N. By convention, ord(X) is called the ordinal
number of X. The notions defined below rely on this convention.
Definition 2.8 (Π-Canonical Variables and Terms)
1. A variable X is called Π-canonical iff there is no other variable X 0 such that
X ≈Π X 0 and ord(X 0 ) < ord(X).
2. For each variable X its Π-canonical form cfΠ (X) is defined as the member of
the set {X 0 ∈ Var | X ≈Π X 0 } with the least ordinal number.
3. A term t is called Π-canonical iff all the variables occurring in t are Πcanonical.
4. For each term t its Π-canonical form cfΠ (t) is defined as the result of replacing
cfΠ (X) for each variable X occurring in t.
The following lemma states some obvious properties of terms in canonical form:
Lemma 2.3 (Π-Canonicity Lemma)
For each term t, cfΠ (t) is Π-canonical and such that t ≈ Π cfΠ (t). Moreover, t and
cfΠ (t) have the same positions and structure, except that each variable X occurring
at some position p ∈ vpos(t) is replaced by an occurrence of cfΠ (X) at the same
position p in cfΠ (t).
Proof
Straightforward consequence of the construction of cfΠ (t) from t and the Π-Equivalence Lemma 2.2.
Given two terms t and s, the term built from t by replacing within t each variable
X occurring at some position p ∈ vpos(t) ∩ pos(s) by the subterm s|p is called the
extension of t w.r.t. to s and noted as t  s (or equivalently, s  t). A more precise
definition of this notion and some related properties are given below.
Definition 2.9 (Term extension)
Given any two terms t and s, the extension of t w.r.t. s is defined by recursion on
the syntactical structure of t:
• X  s = s for each variable X ∈ Var.
• u  s = u for each basic value u ∈ B.

Fixpoint & Proof-theoretic Semantics for SQCLP

11

• c(t1 , . . . , tn )  s = c(t1  s1 , . . . , tn  sn ) if c ∈ DC n and there is some
c0 ∈ DC n such that s = c0 (s1 , . . . , sn ).
• c(t1 , . . . , tn )  s = c(t1 , . . . , tn ) if c ∈ DC n and there is no c0 ∈ DC n such
that s = c0 (s1 , . . . , sn ).
Lemma 2.4 (Extension Lemma)
The term extension operation  enjoys the two following properties:
1. Symmetrical Extension Property:
Let t0 , t00 be Π-canonical terms such that t0 ≈Π t00 . Under this assumption
(t0  t00 ) = (t00  t0 ).
2. Π-Equivalence Extension Property:
Let the terms t, s be such that for any p ∈ pos(t) with t|p = X ∈ Var one has
p ∈ pos(s) and X ≈Π s|p . Under this assumption t ≈Π (t  s).
Proof of Symmetrical Extension Property
Recall that the hypothesis t0 ≈Π t00 means that Π |=C t0 == t00 . We reason by
complete induction on kt0 k + kt00 k. There are five possible cases:
1. t0 == t00 is c0 (t0 n ) == c00 (t00 n ) for some n ∈ N, c0 , c00 ∈ DC n . In this case, the
Π-Equivalence Lemma 2.2 ensures that c0 = c00 = c ∈ DC n and t0i ≈Π t00i holds for
all 1 ≤ i ≤ n. Clearly, the terms t0i , t00i are Π-canonical. Therefore, by induction
hypothesis we can assume (t0i  t00i ) = (t00i  t0i ) for all 1 ≤ i ≤ n. Then, by
definition of  we get t0  t00 = c(t01  t001 , . . . , t0n  t00n ) = c(t001  t01 , . . . , t00n 
t0n ) = t00  t0 .
2. t0 == t00 is u0 == u00 for some u0 , u00 ∈ B. In this case, u0 ≈Π u00 implies that
u0 = u00 = u ∈ B, and by definition of  we get t0  t00 = t00  t0 = u  u = u.
3. t0 == t00 is X == Y for some X, Y ∈ Var. In this case, X ≈Π Y and X, Y Πcanonical implies that X, Y must be identical variables. By definition of  we get
t0  t00 = t00  t0 = X  X = X.
4. t0 == t00 is X == t00 with X ∈ Var, t00 ∈
/ Var. In this case, by definition of  we
0
00
00
00
00
0
get t  t = X  t = t and t  t = t00  X = t00 .
5. t0 == t00 is t0 == Y with Y ∈ Var, t0 ∈
/ Var. In this case, by definition of  we get
t0  t00 = t0  Y = t0 = t00 and t00  t0 = Y  t0 = t0 .
Proof of Π-Equivalence Extension Property
Recall that the thesis t ≈Π (t  s) means that Π |=C t == (t  s). We reason by
complete induction on ktk. There are four possible cases:
1. t is a variable X ∈ Var. In this case, X  s = s by definition of , and X ≈Π s
holds by hypothesis.
2. t is a basic value u ∈ B. In this case, u  s = u by definition of , and u ≈Π u
holds trivially.
3. t is c(tn ) for some c ∈ DC n and there is no c0 ∈ DC n such that s has the form
c0 (sn ). In this case, c(tn )  s = c(tn ) by definition of , and c(tn ) ≈Π c(tn ) holds
trivially.

12

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

4. t is c(tn ) for some c ∈ DC n and s is c0 (sn ) for some c0 ∈ DC n . In this case c(tn ) 
c0 (sn ) = c(t1  s1 , . . . , tn  sn ) by definition of . Moreover, the assumptions of
the Π-Equivalent Extension Property hold for the smaller terms ti , si (1 ≤ i ≤ n).
By induction hypothesis we can assume ti ≈Π (ti  si ) for all 1 ≤ i ≤ n. Therefore,
c(tn ) ≈Π c(t1  s1 , . . . , tn  sn ) due to the Π-Equivalence Lemma 2.2.

2.2 Qualification Domains
The intended role of Qualification Domains in an extended logic programming
scheme SQCLP have been already explained in the Introduction. They were originally introduced in (Rodrı́guez-Artalejo and Romero-Dı́az 2008b) and their axiomatic definition was extended with axioms for an additional operation
in
(Rodrı́guez-Artalejo and Romero-Dı́az 2009) in order to enable a particular implementation technique for program clauses with threshold conditions in their bodies.
The definition given below is again closer to the original one: is omitted and the
axioms of the operator ◦ are slightly refined.
Definition 2.10 (Qualification Domains)
A Qualification Domain is any structure D = hD, P, b, t, ◦i verifying the following
requirements:
1. D, noted as DD when convenient, is a set of elements called qualification
values.
2. hD, P, b, ti is a lattice with extreme points b (called infimum or bottom element) and t (called maximum or top element) w.r.t. the partial ordering P,
called qualification ordering. For given elements d, e ∈ D, we write d u e for
the greatest lower bound (glb) of d and e, and d t e for the least upper bound
(lub) of d and e. We also write d C e as abbreviation for d P e ∧ d 6= e.
3. ◦ : D × D → D, called attenuation operation, verifies the following axioms:
(a)
(b)
(c)
(d)
(e)

◦ is associative, commutative and monotonic w.r.t. P.
∀d ∈ D : d ◦ t = d.
∀d ∈ D : d ◦ b = b.
∀d, e ∈ D : d ◦ e P e.
∀d, e1 , e2 ∈ D : d ◦ (e1 u e2 ) = (d ◦ e1 ) u (d ◦ e2 ).

Actually, some of the properties of ◦ postulated as axioms in the previous definition are redundant.2 More precisely:
Proposition 2.1 (Redundant postulates of Qualification Domains)
The properties (3)(c) and (3)(d) are redundant and can be derived from the other
axioms in Definition 2.10.

2

The authors are thankful to G. Gerla for pointing out this fact.

Fixpoint & Proof-theoretic Semantics for SQCLP

13

Proof
Note that ◦ is commutative and monotonic w.r.t. P because of axiom (3)(a). Since
t is the top element of the lattice, d P t holds for any d ∈ D. By monotonicity of
◦, d ◦ e P t ◦ e also holds for any e ∈ D. By commutativity of ◦ and axiom (3)(b),
d ◦ e P t ◦ e is the same as d ◦ e P e. Therefore (3)(d) is a consequence of the other
axioms postulated for ◦. In particular, taking e = b we get d ◦ b P b, which implies
d ◦ b = b because b is the bottom element of the lattice. Hence, (3)(c) also follows
form the other axioms.
In the rest of the report, D will generally denote an arbitrary qualification domain. For any finite S = {e1 , e2 , . . . , en } ⊆ D, the greatest lower bound (also called
d
infimum of S and noted as S) exists and can be computed as e1 u e2 u · · · u en
(which reduces to > in the case n = 0). The dual claim concerning least upper
bounds is also true. As an easy consequence of the axioms, one gets the identity
d
d
d ◦ S = {d ◦ e | e ∈ S}.
Many useful qualification domains are such that ∀d, e ∈ D \ {b} : d ◦ e 6= b.
In the sequel, any qualification domain D that verifies this property will be called
stable. Below we present some basic qualification domains which are clearly stable,
along with brief explanations of their role for building extended CLP languages
as instances of the SQCLP scheme proposed in this report. Checking that these
domains satisfy the axioms given in Def. 2.10 is left as an easy exercise. In fact,
the axioms have been chosen as a natural generalization of some basic properties
satisfied by the ordering ≤ and the operation × over the real interval [0, 1].
2.2.1 The Domain B of Classical Boolean Values
This domain is B =def h{0, 1}, ≤, 0, 1, ∧i, 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}.
2.2.2 The Domain U of Uncertainty Values and its variant U 0
This domain is U =def hU, ≤, 0, 1, ×i, where U = [0, 1] = {d ∈ R | 0 ≤ d ≤ 1},
≤ is the usual numerical ordering, and × is the multiplication operation. The top
d
element t is 1 and the greatest lower bound S of a finite S ⊆ U is the minimum
value min(S), which is 1 if S = ∅. Elements of U are intended to represent certainty
degrees as used in (van Emden 1986).
A slightly different domain U 0 can be defined as hU, ≤, 0, 1, mini where the only
difference with respect to U is that in the case of U 0 , ◦ = min.
2.2.3 The Domain W of Weight Values and related variants
This domain is W =def hP, ≥, ∞, 0, +i, 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). The top

14

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

d
element t is 0 and the greatest lower bound S of a finite S ⊆ P is the maximum
value max(S), which is 0 if S = ∅. Elements of W are intended to represent proof
costs, measured as the weighted depth of proof trees.
In analogy to the definition of U 0 as a variant of U, we can define a qualification
domain W 0 as hP, ≥, ∞, 0, maxi with ◦ = max. Also, as a discrete variant of W,
we define the qualification domain Wd =def hP, ≥, ∞, 0, +i with the only difference
w.r.t. W being that P = N ∪ {∞}. Elements of Wd are also intended to represent
proof costs (represented by natural numbers in this case). Finally, a variant Wd0 of
Wd can be defined by replacing the attenuation operation in Wd by max.

2.2.4 Two product constructions
To close this section, we present two product constructions that can be used to
build compound qualification domains. The mathematical definition is as follows:
Definition 2.11 (Products of Qualification Domains)
Let two qualification domains Di = hDi , Pi , bi , ti , ◦i i (i ∈ {1, 2}) be given.
1. The cartesian product D1 × D2 is defined as D =def hD, P, b, t, ◦i where
D =def D1×D2 , the partial ordering P is defined as (d1 , d2 ) P (e1 , e2 ) ⇐⇒def
d1 P1 e1 and d2 P2 e2 , b =def (b1 , b2 ), t =def (t1 , t2 ) and the attenuation
operator ◦ is defined as (d1 , d2 ) ◦ (e1 , e2 ) =def (d1 ◦1 e1 , d2 ◦2 e2 ).
2. Given two elements d1 ∈ D1 and d2 ∈ D2 , the strict pair L d1 , d2 M is defined by
case distinction as follows: if d1 6= b1 and d2 6= b2 , then L d1 , d2 M = (d1 , d2 );
if d1 = b1 or d2 = b2 , then L d1 , d2 M = (b1 , b2 ). In both cases, L d1 , d2 M ∈
D1 × D2 .
3. The strict cartesian product D1 ⊗ D2 is defined as D =def hD, P, b, t, ◦i where
D = D1 ⊗ D2 =def {L d1 , d2 M | d1 ∈ D1 , d2 ∈ D2 } (or equivalently, D =
((D1 \ {b1 }) × (D2 \ {b2 })) ∪ {(b1 , b2 )}), the partial ordering P is defined
as (d1 , d2 ) P (e1 , e2 ) ⇐⇒def d1 P1 e1 and d2 P2 e2 , b =def L b1 , b2 M =
(b1 , b2 ), t =def L t1 , t2 M, and the attenuation operator ◦ is defined as (d1 , d2 )◦
(e1 , e2 ) =def (d1 ◦1 e1 , d2 ◦2 e2 ). Note the special case when D1 or D2 is a
singleton set. Then, D is the singleton set {(b1 , b2 )}, L t1 , t2 M = (b1 , b2 ),
and (t1 , t2 ) ∈ D happens to be false if one of the two sets D1 , D2 is not a
singleton.
Intuitively, each value (d1 , d2 ) belonging to a product domain D1× D2 or D1 ⊗ D2
imposes the qualification d1 and also the qualification d2 . In particular, values (c, d)
belonging to the product domains U × W and U ⊗ W impose two qualifications,
namely: a certainty value greater or equal than c and a proof tree with weighted
depth less or equal than d. This intuition indeed corresponds to the declarative
semantics formally defined in Section 3.
The next theorem shows that the class of the qualification domains is closed under ordinary cartesian products, while the subclass of stable qualification domains
is closed under strict cartesian products. We are particularly interested in stable

Fixpoint & Proof-theoretic Semantics for SQCLP

15

qualification domains built from basic domains by reiterated strict products, because they can be encoded into into constraint domains in the sense explained in
Subsection 2.2.5 below.
Theorem 2.1
Assume two given qualification domains D1 and D2 . Then the ordinary cartesian
product D1×D2 is always a qualification domain. Moreover, if D1 and D2 are stable,
then the strict cartesian product D1 ⊗ D2 is a stable qualification domain.
Proof
Here we reason only for the case of the strict cartesian product since the reasonings
needed for the ordinary cartesian product are very similar and even simpler. Assume
that D1 and D2 are stable qualification domains, and let D = D1 ⊗D2 be constructed
as in Definition 2.11. In order to show that D is a stable qualification domain, we
prove the four items below. The assumption that D1 and D2 satisfy all the axioms
from Definition 2.10 is used in all the reasonings, often implicitly.
1. The attenuation operator ◦ of D is well defined. Assume (d1 , d2 ), (e1 , e2 ) ∈ D.
According to Definition 2.11, (d1 , d2 ) ◦ (e1 , e2 ) is defined as (d1 ◦1 e1 , d2 ◦2 e2 ). Since
D = D1 ⊗D2 is a strict subset of D1 ×D2 , we must prove that (d1 ◦1 e1 , d2 ◦2 e2 ) ∈ D.
We reason by distinction of cases:
1.1. (d1 , d2 ) = (b1 , b2 ) or (e1 , e2 ) = (b1 , b2 ). In this case, (d1 ◦1 e1 , d2 ◦2 e2 ) =
(b1 , b2 ) ∈ D.
1.2. (d1 , d2 ) 6= (b1 , b2 ) and (e1 , e2 ) 6= (b1 , b2 ). In this case, d1 , e1 ∈ D1 \ {b1 }
and d2 , e2 ∈ D2 \ {b2 }. The assumption that D1 and D2 are stable ensures
d1 ◦1 e1 6= b1 and d2 ◦2 e2 6= b2 , and therefore (d1 ◦1 e1 , d2 ◦2 e2 ) ∈ D.
2. hD, P, b, ti is a lattice with extreme points b = L b1 , b2 M = (b1 , b2 ) and t =def L t1 ,
t2 M w.r.t. the partial ordering P. By definition, (d1 , d2 ) P (e1 , e2 ) ⇐⇒ d1 P1
e1 ∧d2 P2 e2 . The fact that P is a partial ordering with minimum (bottom) element
b is an obvious connsequence. To prove that t is the maximum (top) element, we
reason by case distinction. If D1 is a singleton set, then D1 = {b1 }, t1 = b1 ,
D = {(b1 , b2 )}, and L t1 , t2 M = (b1 , b2 ) is obviously the top element. The case that
D2 is a singleton set is argued similarly. Finally, if neither D1 nor D2 are singleton,
we have t1 6= b1 , t2 6= b2 , and t = L t1 , t2 M = (t1 , t2 ) is clearly the top element.
To show that hD, P, b, ti is a lattice, we assume two arbitrary elements (d1 , d2 ),
(e1 , e2 ) ∈ D, and we prove:
2.1. There is a lub (d1 , d2 ) t (e1 , e2 ) ∈ D. The lubs d1 t1 e1 ∈ D1 and d2 t2 e2 ∈ D2
are known to exist. We claim that (d1 , d2 )t(e1 , e2 ) = (d1 t1 e1 , d2 t2 e2 ). Due to
the component-wise definition of P, it suffices to show that (d1 t1 e1 , d2 t2 e2 ) ∈
D. We prove this by case distinction:
2.1.1. If (d1 , d2 ) = (b1 , b2 ) then (d1 t1 e1 , d2 t2 e2 ) = (e1 , e2 ) ∈ D.
2.1.2. If (e1 , e2 ) = (b1 , b2 ) then (d1 t1 e1 , d2 t2 e2 ) = (d1 , d2 ) ∈ D.
2.1.3. If (d1 , d2 ) 6= (b1 , b2 ) and (e1 , e2 ) 6= (b1 , b2 ) then the construction of D
ensures that d1 , e1 ∈ D1 \ {b1 } and d2 , e2 ∈ D2 \ {b2 }. This implies
d1 t1 e1 6= b1 and d2 t2 e2 6= b2 , which guarantees (d1 t1 e1 , d2 t2 e2 ) ∈ D.

16

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

2.2. There is a glb (d1 , d2 ) u (e1 , e2 ) ∈ D. The glbs d1 u1 e1 ∈ D1 and d2 u2 e2 ∈ D2
are known to exist. We claim that (d1 , d2 ) u (e1 , e2 ) = L d1 u1 e1 , d2 u2 e2 M.
We prove the claim by case distinction:
2.2.1. If d1 u1 e1 6= b1 and d2 u2 e2 6= b2 , then L d1 u1 e1 , d2 u2 e2 M is the same
as (d1 u1 e1 , d2 u e2 ) ∈ D, and this pair is the glb of (d1 , d2 ) and (e1 , e2 )
due to the component-wise definition of P.
2.2.2. If d1 u1 e1 = b1 or d2 u2 e2 = b2 , then L d1 u1 e1 , d2 u2 e2 M = (b1 , b2 )
is obviously a common lower bound of (d1 , d2 ) and (e1 , e2 ). In order to
conclude that (b1 , b2 ) is the glb of (d1 , d2 ) and (e1 , e2 ), we show that
(b1 , b2 ) is the only common lower bound of (d1 , d2 ) and (e1 , e2 ) by the
following reasoning: assume an arbitrary (x, y) ∈ D such that (x, y) P
(d1 , d2 ) and (x, y) P (e1 , e2 ). Then x P d1 u1 e1 and y P d2 u2 e2 . Since
d1 u1 e1 = b1 or d2 u2 e2 = b2 , it follows that x = b1 or y = b2 . By
construction of D, it must be the case that x = b1 and y = b2 , because
otherwise (x, y) would not belong to D. Therefore (x, y) = (b1 , b2 ), as
desired.
3. ◦ satisfies axioms required for attenuation operators in Definition 2.10. By definition
of ◦ we know
(?) (d1 , d2 ) ◦ (e1 , e2 ) = (d1 ◦1 e1 , d2 ◦2 e2 )
which always belongs to D as already proved in item (1) above. All the axioms listed
under item (3) of Definition 2.10 except (3)(e) follow easily from the equation (?)
and the corresponding axioms for ◦1 and ◦2 . In order to verify axiom (3)(e) for ◦,
we assume three pairs (d1 , d2 ), (e1 , e2 ), (e01 , e02 ) ∈ D. We must prove the equation
(†) (d1 , d2 ) ◦ ((e1 , e2 ) u (e01 , e02 )) = (d1 , d2 ) ◦ (e1 , e2 ) u (d1 , d2 ) ◦ (e01 , e02 ) .
We reason by case distinction:
3.1. If d1 = b1 and d2 = b2 then both sides of (†) are equal to (b1 , b2 ), as shown
by the following calculations:
(d1 , d2 ) ◦ ((e1 , e2 ) u (e01 , e02 )) = (b1 , b2 ) ◦ ((e1 , e2 ) u (e01 , e02 )) = (b1 , b2 )
(d1 , d2 ) ◦ (e1 , e2 ) u (d1 , d2 ) ◦ (e01 , e02 ) =
(b1 , b2 ) ◦ (e1 , e2 ) u (b1 , b2 ) ◦ (e01 , e02 ) = (b1 , b2 ) u (b1 , b2 ) = (b1 , b2 )
3.2. If the previous case does not apply, the construction of D ensures that d1 6= b1
and d2 6= b2 . We distiguish two subcases:
3.2.1. If e1 u1 e01 = b1 or e2 u2 e02 = b2 we get also d1 ◦1 (e1 u1 e01 ) = b1 or
d2 ◦2 (e2 u2 e02 ) = b2 , and we can assume the following:
(♣) L e1 u1 e01 , e2 u2 e02 M = (b1 , b2 )
(♠) L d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ) M = (b1 , b2 )

Fixpoint & Proof-theoretic Semantics for SQCLP

17

We can now prove that both sides of (†) are equal to (b1 , b2 ) as follows:
(d1 , d2 ) ◦ ((e1 , e2 ) u (e01 , e02 )) =
(d1 , d2 ) ◦ L e1 u1 e01 , e2 u2 e02 M =♣ (d1 , d2 ) ◦ (b1 , b2 ) = (b1 , b2 )
(d1 , d2 ) ◦ (e1 , e2 ) u (d1 , d2 ) ◦ (e01 , e02 ) =
(d1 ◦1 e1 , d2 ◦2 e2 ) u (d1 ◦1 e01 , d2 ◦2 e02 ) =
L d1 ◦1 e1 u1 d1 ◦1 e01 , d2 ◦2 e2 u2 d2 ◦2 e02 M =
L d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ) M =♠ (b1 , b2 )

3.2.2. If e1 u1 e01 6= b1 and e2 u2 e02 6= b2 then the stability assumption made for
D1 and D2 ensures d1 ◦1 (e1 u1 e01 ) 6= b1 and d2 ◦2 (e2 u2 e02 ) 6= b2 , and we
can assume the following:
(♦) L e1 u1 e01 , e2 u2 e02 M = (e1 u1 e01 , e2 u2 e02 )
(♥) L d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ) M = (d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ))

Then, (†) is proved by the following calculations:

(d1 , d2 ) ◦ ((e1 , e2 ) u (e01 , e02 )) =
(d1 , d2 ) ◦ L e1 u1 e01 , e2 u2 e02 M =♦ (d1 , d2 ) ◦ (e1 u1 e01 , e2 u2 e02 ) =
(d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ))
(d1 , d2 ) ◦ (e1 , e2 ) u (d1 , d2 ) ◦ (e01 , e02 ) =
(d1 ◦1 e1 , d2 ◦2 e2 ) u (d1 ◦1 e01 , d2 ◦2 e02 ) =
L d1 ◦1 e1 u1 d1 ◦1 e01 , d2 ◦2 e2 u2 d2 ◦2 e02 M =
L d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ) M =♥
(d1 ◦1 (e1 u1 e01 ), d2 ◦2 (e2 u2 e02 ))
4. D1⊗D2 is stable. To prove this let us assume (d1 , d2 ), (e1 , e2 ) ∈ D1 ⊗D2 \{(b1 , b2 )}.
Then d1 , e1 ∈ D1 \ {b1 } and d2 , e2 ∈ D2 \ {b2 }. Since D1 and D2 are stable
qualification domains, we can infer that d1 ◦1 e1 6= b1 and d2 ◦2 e2 6= b2 , which
implies (d1 , d2 ) ◦ (e1 , e2 ) = (d1 ◦1 e1 , d2 ◦2 e2 ) 6= (b1 , b2 ).
2.2.5 Encoding Qualification Domains into Constraint Domains
In this subsection we investigate a technical relationship between qualification domains and constraint domains which will play a key role in the rest of the report.
Definition 2.12 (Expressing D in C)
A qualification domain D with carrier set DD is expressible in a constraint domain
C with carrier set CC if there is an injective mapping ı : DD \ {b} → CC embedding
DD \ {b} into CC , and the two following requirements are satisfied:
1. There is a C-constraint qVal(X) such that SolC (qVal(X)) is the set of all
η ∈ ValC such that η(X) belongs to the range of ı.
2. There is a C-constraint qBound(X, Y, Z) encoding “x P y ◦ z” in the following
sense: any η ∈ ValC satisfying η(X) = ı(x), η(Y ) = ı(y) and η(Z) = ı(z) for
some x, y, z ∈ D \ {b} verifies η ∈ SolC (qBound(X, Y, Z)) ⇐⇒ x P y ◦ z.

Moreover, if qVal(X) and qBound(X, Y, Z) can be chosen as existential constraints,
we say that D is existentially expressable in C.

18

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

In the sequel, C-constraints built as instances of qVal(X) and qBound(X, Y, Z) are
called qualification constraints, and Ω is used as notation for sets of qualification
constraints. The following result ensures that several qualification domains built
with the techniques presented in Subsection 2.2 are existentially expressible in H,
R or FD, according to the case.
Proposition 2.2 (Expressing Qualification Domains in Constraint Domains)
1. The domain B is existentially expressible in any given constraint domain C.
2. The domains U, U 0, W and W 0 are existentially expressible in R (or any other
constraint domain that supports the expressivity of R).
3. The domains Wd and Wd0 are existentially expressible in FD (or any other
constraint domain that supports the expressivity of FD).
4. Assume that the two qualification domains D1 and D2 are stable and (existentially) expressible in a constraint domain C. Then, D1 ⊗ D2 is also (existentially) expressible in C.
Proof
1. Straightforward, due to the fact that DB \ {b} is the singleton set {t} = {true}.
2. We prove that U can be existentially expressed in R as follows: DU \ {b} =
DU \ {0} = (0, 1] ⊆ R ⊆ CR ; therefore ı can be taken as the identity embedding mapping from (0, 1] into R. Moreover, qVal(X) can be built as the existential
R-constraint cp< (0, X) ∧ cp≤ (X, 1) and qBound(X, Y, Z) can be built as the existential R-constraint ∃X1 (op× (Y, Z, X1 ) ∧ cp≤ (X, X1 )). By very similar reasonings
it is easy to check that U 0 , W and W 0 can also be existentially expressed in R. Note
that in the cases of W and W 0 there is no reasonable way to define ı(∞). This is
the reason why the domain of ı is required to be D \ {b} in Definition 2.12.
3. Note that DWd \ {b} = DWd \ {∞} = N. Moreover, P is ≥ and ◦ is + in Wd .
Therefore, Wd can be expressed in FD by taking ı as the identity embedding
mapping, building qVal(X) as an existential FD constraint that requires the value
of X to be an integer x ≥ 0, and building qBound(X, Y, Z) as an existential FD
constraint that requires the values of X, Y and Z to be integers x, y and z such
that x ≥ y + z. A similar reasoning proves that Wd0 is existentially expressible in
FD also.
4. For j = 1, 2 assume the existence of injective embedding mappings ıj and Cconstraints qValj (X), qBoundj (X, Y, Z) that can be used to (existentially) express
Dj in C. Due to Theorem 2.1 we know that D1 ⊗ D2 is a stable qualification domain. Moreover, because of the construction of D = D1 ⊗ D2 given in Definition
2.11, we know that D \ {b} = (D1 \ {b1 }) × (D2 \ {b2 }). We also know that P is
defined component-wise from P1 , and P2 , and analogously for ◦. Therefore, D can
be (existentially) expressed in C by taking:
• ı defined by ı(d1 , d2 ) =def (ı1 (d1 ), ı2 (d2 )).
• qVal(X) built as the prenex form of the constraint
∃X1 ∃X2 (X == (X1 , X2 ) ∧ qVal1 (X1 ) ∧ qVal2 (X2 ))
which is existential if qVal1 (X1 ) and qVal2 (X2 ) are both existential.

Fixpoint & Proof-theoretic Semantics for SQCLP

19

• qBound(X, Y, Z) built as the prenex form of the constraint
∃X1 ∃X2 ∃Y1 ∃Y2 ∃Z1 ∃Z2 (X == (X1 , X2 ) ∧ Y == (Y1 , Y2 ) ∧ Z == (Z1 , Z2 )∧
qBound1 (X1 , Y1 , Z1 ) ∧ qBound2 (X2 , Y2 , Z2 ))
which is existential if qBound1 (X1 , Y1 , Z1 ) and qBound2 (X2 , Y2 , Z2 ) are both
existential.
Note that this reasoning does not work for the non-strict cartesian product D =
D1 × D2 , because in this case D \ {b} = (D1 × D2 ) \ {(b1 , b2 )} includes some pairs
(d1 , d2 ) such that either d1 = b1 or d2 = b2 (but not both), and the given mappings
ı1 , ı2 cannot be used to embed such pairs into CC .
2.3 Similarity and Proximity Relations
Similarity relations over a given set S have been defined in (Zadeh 1971; Sessa
2002) and related literature as mappings S : S × S → [0, 1] that satisfy reflexivity,
symmetry and transitivity axioms analogous to those required for classical equivalence relations. A more general notion called proximity relation has been defined
in (Dubois and Prade 1980) by omitting the transitivity axiom. Each value S(x, y)
computed by a similarity (resp. proximity) relation S is called the similarity degree
(resp. proximity degree) between x and y. In our previous paper (Caballero et al.
2008), we proposed to generalize similarity relations by allowing elements of an arbitrary qualification domain D to serve as proximity degrees. The definition below
further generalizes this approach by considering proximity relations.
Definition 2.13 (Proximity and similarity relations)
Let a qualification domain D with carrier set D and a set S be given.
1. A D-valued relation over S is any mapping S : S × S → D.
2. A D-valued relation S over S is called
(a) Reflexive iff ∀x ∈ S : S(x, x) = t.
(b) Symmetrical iff ∀x, y ∈ S : S(x, y) = S(y, x).
(c) Transitive iff ∀x, y, z ∈ S : S(x, z) Q S(x, y) u S(y, z).
3. S is called a D-valued proximity relation iff S is reflexive and symmetrical.
4. If S is also transitive, then it is called a D-valued similarity relation.
5. S is called finitary iff there are only finitely many choices of elements x, y ∈ S
such that x 6= y and S(x, y) 6= b. From a practical viewpoint, this is a very
natural requirement.
Obviously, D-valued similarity relations are a particular case of D-valued proximity relations. Moreover, when D is chosen as the qualification domain U, the previous
definition provides proximity and similarity relations in the sense of (Zadeh 1971;
Dubois and Prade 1980). In this case, a proximity degree S(x, y) = d ∈ [0, 1] can
be naturally interpreted as a certainty degree for the assertion that x and y are
interchangeable. On the other hand, if S is W-valued, then S(x, y) = d ∈ [0, ∞]
can be interpreted as a cost to be paid for y to play the role of x. More generally, the

20

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

proximity degrees computed by a D-valued proximity relation may have different
interpretations according to the intended role of D-elements as qualification values.
In contrast to previous works such as (Sessa 2002; Caballero et al. 2008), in the
rest of this report we will work with D-valued proximity rather than similarity
relations. Formally, this leads to more general results. Moreover, as already noted
by (Shenoi and Melton 1999) and other authors, the transitivity property required
for similarity relations may be counterintuitive in some cases. For instance, assume nullary constructors colt, cold and gold intended to represent words composed of four letters. Then, measuring the proximity between such words might
reasonably lead to a U-valued proximity relation S such that S(colt, cold) = 0.9,
S(cold, gold) = 0.9 and S(colt, gold) = 0.4. On the other hand, insisting on
S to be transitive would enforce the unreasonable condition S(colt, gold) ≥ 0.9.
Therefore, a similarity relation would be not appropriate in this case.
The special mapping Sid : S × S → D defined as Sid (x, x) = t for all x ∈ S and
Sid (x, y) = b for all x, y ∈ S, x 6= y is trivially a D-valued similarity (and therefore,
also proximity) relation called the identity.
2.3.1 Admissible triples and proximity relations
From now on, we will focus on proximity relations that are related to constraint
domains in the following sense:
Definition 2.14 (Admissible triples)
hS, D, Ci is called an admissible triple iff the following requirements are fulfilled:
1. C is a constraint domain with signature Σ = hDC, DP, P P i and set of basic
values BC , and D is a qualification domain expressible in C in the sense of
Definition 2.12.
2. S is a D-valued proximity relation over S = Var ] BC ] DC ] DP ] P P .
3. S restricted to Var behaves as the identity, i.e. S(X, X) = t for all X ∈ Var
and S(X, Y ) = b for all X, Y ∈ Var such that X 6= Y .
4. For any x, y ∈ S, S(x, y) 6= b can happen only if some of the following cases
holds:
(a)
(b)
(c)
(d)

x = y are identical.
x, y ∈ BC are basic values.
x, y ∈ DC are data constructor symbols with the same arity.
x, y ∈ DP are defined predicate symbols with the same arity.

In particular, S(p, p0 ) 6= b cannot happen if p, p0 ∈ P P are syntactically
different primitive predicate symbols.
In the rest of the report, our notions and results are valid for any choice of an
admissible triple hS, D, Ci. Proposition 2.2 provides useful information for building
admissible triples. For any given admissible triple, S can be naturally extended to
act over terms and atoms over C. The extension, also noted S, works as specified
in the recursive definition below. An analogous definition for the case of U-valued
similarity relations can be found in (Sessa 2002).

Fixpoint & Proof-theoretic Semantics for SQCLP

21

Definition 2.15 (S acting over terms and atoms)
For any given admissible triple, S is extended to work over C-terms and C-atoms
as follows:
1. For any t ∈ Term(Σ, B, Var):
S(t, t) = t.
2. For X ∈ Var and for any term t different from X:
S(X, t) = S(t, X) = b.
3. For c, c0 ∈ DC with different arities n, m:
S(c(tn ), c0 (t0 m )) = b.
4. For c, c0 ∈ DC with the same arity n:
S(c(tn ), c0 (t0 n )) = S(c, c0 ) u S(t1 , t01 ) u . . . u S(tn , t0n ).
5. For r, r0 ∈ DP ∪ P P with different arities n, m:
S(r(tn ), r0 (t0 m )) = b.
6. For r, r0 ∈ DP ∪ P P with the same arity n:
S(r(tn ), r0 (t0 n ) = S(r, r0 ) u S(t1 , t01 ) u . . . u S(tn , t0n ).
Given two terms t, t0 and some fixed qualification value λ ∈ D \ {b} we will use
the notation t ≈λ t0 (read as t and t0 are S-close at level λ) as an abbreviation of
λ P S(t, t0 ). For the sake of simplicity, S is not made explicit in the ≈λ notation.
The following lemma provides a natural characterization of ≈λ . A similar result
was given in (Sessa 2002) for the case of case of U-valued similarity relations.
Lemma 2.5 (Proximity Lemma)
1. ≈λ is a reflexive and symmetric equivalence relation over terms, which is also
transitive (and hence an equivalence relation) in the case that S is a similarity
relation.
2. For any given terms t and t0 the following two statements are equivalent:
(a) t ≈λ t0 .
(b) pos(t) = pos(t0 ), and for each p ∈ pos(t) ∩ pos(t0 ) some of the
cases below holds:
i t ◦ p = t0 ◦ p = X for some X ∈ Var.
ii t ◦ p = s ◦ p = u for some u ∈ BC .
iii t ◦ p = c and t0 ◦ p = c0 for some n ∈ N and some
c, c0 ∈ DC n such that λ P S(c, c0 ).
3. Any given terms t and t0 such that t ≈λ t0 are quasi-identical in the following
sense: pos(t) = pos(t0 ), and for each p ∈ pos(t) = pos(t0 ) either t ◦ p = t0 ◦ p
or else t ◦ p and t0 ◦ p are two data constructors of the same arity.
4. ≈λ boils down to the syntactic equality relation ‘=’ when S is the identity
proximity relation Sid .
Proof
We give a separate reasoning for each item.

22

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

1. Note that the reflexivity and symmetry of ≈λ are a trivial consequence of the
reflexivity and symmetry of S, as formulated in Definition 2.13. In the case that
S is a similarity relation, transitivity of ≈λ follows from transitivity of S and the
obvious fact that λ u λ = λ.
2. The claimed equivalence between conditions 2(a) and 2(b) can be proved reasoning
by induction on ktk + kt0 k.
3. This item is an obvious consequence of the previous one.
4. Assume S = Sid . Then, as a trivial consequence of Definition 2.15, the value of
S(t, t0 ) is t if t = t0 and b otherwise. Since λ 6= b, it follows that t ≈λ t0 iff t = t0 ,
as desired.
The following result shows that ≈λ is compatible with the term extension operation in a natural way:
Lemma 2.6 (Proximity Preservation Lemma)
Assume terms t, t0 and λ ∈ D \ {b} such that t ≈λ t0 . Then (t  s) ≈λ (t0  s)
holds also for any term s.
Proof
Due to the assumption, t ≈λ t0 are quasi-identical and satisfy condition 2(b) as
stated in the Proximity Lemma 2.5. From this fact and Definition 2.9 it is quite
clear that the same condition 2(b) holds also for t  s, t0  s and λ. Therefore,
the Proximity Lemma allows to conclude t ≈λ t0 as desired.
2.3.2 Term proximity w.r.t. a given constraint set
Reasoning with equations between C-terms will require to infer information both
from S and for some fixed constraint set Π ⊆ ConC . This leads to a generalization
of ≈λ formally defined as follows:
Definition 2.16 (Term proximity w.r.t. a given constraint set)
Let hS, D, Ci be any admissible triple. Assume λ ∈ D \ {b} and Π ⊆ ConC . We
will say that t and s are S-close at level λ w.r.t. Π (in symbols, t ≈λ,Π s) iff there
are two terms t̂, ŝ such that t ≈Π t̂, s ≈Π ŝ and t̂ ≈λ ŝ. For the sake of simplicity
neither S nor C are made explicit in the notation.
As illustration, let us present an example using the constraint domain R and the
qualification domain U:
Example 2.2 (Term proximity w.r.t. R constraints)
Consider Π = {op+ (A, A, X), op× (2.0, A, Y ), Z == c(X, Y )} ⊆ ConR . Note that
this choice of Π ensures X ≈Π Y . Assume c, c0 , c00 ∈ DC 2 and an U-valued proximity
relation S such that S(c0 , c) = S(c, c00 ) = 0.8 and S(c0 , c00 ) = 0.6. Then:
1. c(Y, X) ≈Π Z holds, but c0 (Y, X) ≈Π Z is false.
2. c0 (Y, X) ≈0.7,Π Z holds, because c0 (Y, X) ≈Π c0 (X, X), Z ≈Π c(X, X) and
c0 (X, X) ≈0.7 c(X, X).
3. Z ≈0.7,Π c00 (X, Y ) is also true, for similar reasons.

Fixpoint & Proof-theoretic Semantics for SQCLP

23

4. c0 (Y, X) ≈0.7,Π c00 (X, Y ) is false, because there is no possible choice of terms
t̂ and ŝ such that c0 (Y, X) ≈Π t̂, c00 (X, Y ) ≈Π ŝ and t̂ ≈0.7 ŝ.
The next result states some basic properties of relations ≈λ,Π .
Lemma 2.7 (Π-Proximity Lemma)
1. ≈λ,Π is invariant w.r.t. ≈Π in the following sense: t ≈λ,Π s implies t0 ≈λ,Π s0
for all terms t0, s0 such that t0 ≈Π t and s0 ≈Π s.
2. ≈λ,Π is a reflexive and symmetric relation over terms, which is also transitive
(and hence an equivalence relation) in the case that S is a similarity relation.
3. For any given terms t and t0 the following two statements are equivalent:
(a) t ≈λ,Π t0 .
(b) For any common position p ∈ pos(t) ∩ pos(t0 ) some of the cases
below holds:
i t ◦ p or t0 ◦ p is a variable, and moreover t|p ≈λ,Π t0 |p .
ii t ◦ p = s ◦ p = u for some u ∈ BC .
iii t ◦ p = c and t0 ◦ p = c0 for some n ∈ N and some
c, c0 ∈ DC n such that λ P S(c, c0 ).
4. ≈λ,Π boils down to ≈λ when Π is the empty set, and ≈λ,Π boils down to ≈Π
when S is the identity proximity relation Sid .
Proof
We give a separate reasoning for each item. Definition 2.16 and Lemmata 2.2 and
2.5 are implicitely used at some points.
1. By definition, t ≈λ,Π s means the existence of terms t̂, ŝ such that t ≈Π t̂, s ≈Π ŝ
and t̂ ≈λ ŝ. In case that t0 ≈Π t and s0 ≈Π s, the same terms t̂, ŝ verify t0 ≈Π t̂,
s0 ≈Π ŝ (since ≈Π is an equivalence relation) and t̂ ≈λ ŝ. Therefore t0 ≈λ,Π s0 .
2. Let us consider the three properties in turn:
Reflexivity: t ≈λ,Π t holds because t̂ = t trivially verifies t ≈Π t̂ and t̂ ≈λ t̂.
Symmetry: Assume t ≈λ,Π s. Then there are terms t̂, ŝ such that t ≈Π t̂, s ≈Π ŝ
and t̂ ≈λ ŝ. Due to the symmetry of ≈λ we get ŝ ≈λ t̂ and hence s ≈λ,Π t.
Transitivity: Example 2.2 above shows that ≈λ,Π is not transitive in general. Here
we prove transitivity of ≈λ,Π under the assumption that S is a similarity relation
fulfilling the transitive property stated in Definition 2.13.
Assume terms t1 , t2 and t3 such that t1 ≈λ,Π t2 and t2 ≈λ,Π t3 . Then there are
terms t01 , t02 , t002 and t003 such that
(a) t1 ≈Π t01 , t2 ≈Π t02 , t01 ≈λ t02

and

(b) t2 ≈Π t002 , t3 ≈Π t003 , t002 ≈λ t003 .

Without loss of generality, t01 , t02 , t002 and t003 can be assumed to be Π-canonical terms.
If they were not, it would suffice to to replace each of them by its Π-canonical form,
built as explained in Definition 2.8. This replacement would preserve properties (a)
and (b) thanks to the Canonicity Lemma 2.3.
We claim that there are three terms tˆ1 , tˆ2 , and tˆ3 such that
(c) t1 ≈Π tˆ1 , t2 ≈Π tˆ2 , t3 ≈Π tˆ3

and

(d) tˆ1 ≈λ tˆ2 , tˆ2 ≈λ tˆ3 .

24

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

Conditions (c) and (d) imply t1 ≈λ,Π t3 due to Definition 2.16 and the transivity
property of ≈λ , which is ensured by the transitivity of S and the Proximity Lemma
2.5. In the rest of this item we prove the claim by assuming (a) and (b) and showing
how to build tˆ1 , tˆ2 , and tˆ3 fulfilling (c) and (d).
Note that the assumption t01 ≈λ t02 implies that t01 and t02 are quasi-identical terms,
due Proximity Lemma 2.5(3). Analogously, terms t002 and t003 must be also quasiidentical due to the assumption t002 ≈λ t003 , and the target condition (d) requires
that tˆ1 , tˆ2 , tˆ3 are constructed as quasi-identical terms. Since our assumptions do
not guarantee quasi-identity of terms t02 and t002 , we resort to the term extension
construction from Definition 2.9 for building the terms tˆi . More precisely, we build:
tˆ1 =def (t01  t002 );

tˆ2 =def (t02  t002 ) = (t002  t02 );

and tˆ3 =def (t003  t02 )

where the identity (t02  t002 ) = (t002  t02 ) is a consequence of the Symmetrical
Extension Property from Lemma 2.4, which can be applied because t02 and t002 are
Π-canonical and assumptions (a), (b) imply t02 ∼Π t002 . We argue that conditions (c)
and (d) are satisfied as follows:
— Condition (c), t1 ≈Π tˆ1 : By assumptions (a), (b) we know t1 ≈Π t01 and t02 ≈Π t002 .
It suffices to prove t01 ≈Π tˆ1 . For each p ∈ pos(t01 ) with t01 |p = X ∈ Var we have
t02 |p = X because t01 and t02 are quasi-identical. Moreover, t02 ≈Π t002 implies that p ∈
pos(t002 ) and X ∼Π t002 |p , due to the Π-Equivalence Lemma 2.2. In these conditions,
t01 ≈Π tˆ1 follows from tˆ1 = (t01  t002 ) and the Equivalent Extension Property from
Lemma 2.4.
— Condition (c), t3 ≈Π tˆ3 : The proof for this is analogous to the previous one.
Since t3 ≈Π t003 and tˆ3 = (t003  t02 ) it suffices to prove t003 ≈Π (t003  t02 ), which can
be done with the help of the Equivalent Extension Property.
— Condition (c), t2 ≈Π tˆ2 : By assumptions (a), (b) we know t2 ≈Π t02 and t02 ≈Π t002 .
It suffices to prove t02 ≈Π tˆ2 . For each p ∈ pos(t02 ) with t02 |p = X ∈ Var we have
p ∈ pos(t002 ) and X ∼Π t002 |p , due to t02 ≈Π t002 and the Π-Equivalence Lemma 2.2. In
these conditions, t02 ≈Π tˆ2 follows from tˆ2 = (t02  t002 ) and the Equivalent Extension
Property.
— Condition (d), tˆ1 ≈λ tˆ2 : By assumption (a) we have t01 ≈λ t02 . By the Proximity
Preservation Lemma 2.6 this implies (t01  t002 ) ≈λ (t02  t002 ). By construction of
the terms tˆi , this is the same as tˆ1 ≈λ tˆ2 .
— Condition (d), tˆ2 ≈λ tˆ3 : The proof for this is analogous to the previous one.
Assumption (b) provides t002 ≈λ t003 . Then, the Proximity Preservation Lemma guarantees (t002  t02 ) ≈λ (t003  t02 ), which is the same as tˆ2 ≈λ tˆ3 by construction of the
terms tˆi (this time viewing tˆ2 as (t002  t02 ) rather than (t02  t002 ) as in the previous
argumentation).
3. The claimed equivalence between conditions 3(a) and 3(b) can proved reasoning by
induction on ktk + kt0 k.
4. According to Definition 2.16, t ≈λ,Π s is true iff (?) holds, where:
(?) there are terms t̂, ŝ such that t ≈Π t̂, s ≈Π ŝ and t̂ ≈λ ŝ.
Let us argue for the two cases Π = ∅ and S = Sid separately:
• Assume that Π = ∅. Then, due to Π-Equivalence Lemma 2.2(3), (?) can be

Fixpoint & Proof-theoretic Semantics for SQCLP

25

rewritten as
there are terms t̂, ŝ such that t = t̂, s = ŝ and t̂ ≈λ ŝ
which is equivalent to t ≈λ s.
• Assume now that S = Sid . Then, due to Proximity Lemma 2.5(4), (?) can be
rewritten as
there are terms t̂, ŝ such that t ≈Π t̂, s ≈Π ŝ and t̂ = ŝ
which is equivalent to t ≈Π s.
The following technical lemma will be needed later on. Although it is closely
related to Lemma 2.1(2), it needs a separate proof because statements of the form
t ≈λ,Π s are not C-constraints.
Lemma 2.8 (Substitution Lemma for ≈λ,Π )
Let hS, D, Ci be any admissible triple. Assume λ ∈ D \ {b}, Π ⊆ ConC , and two
terms t, s such that t ≈λ,Π s. Then tσ ≈λ,Πσ sσ holds for every C-substitution σ.
Proof
Because of the assumptions and Definition 2.16, there are terms t̂, ŝ such that
t ≈Π t̂ (i.e. Π |=C t == t̂), s ≈Π ŝ (i.e. Π |=C s == ŝ) and t̂ ≈λ ŝ. Consider now
any substitution σ. Due to Lemma 2.1(2), we get Πσ |=C tσ == t̂σ (i.e. tσ ≈Πσ t̂σ)
and Πσ |=C sσ == ŝσ (i.e. sσ ≈Πσ ŝσ). Moreover, t̂σ ≈λ ŝσ is an easy consequence
of t̂ ≈λ ŝ and Proximity Lemma 2.5(2). Then, Definition 2.16 allows to conclude
ˆ and ŝσ as sσ.
tσ ≈λ,Πσ sσ simply by taking t̂σ as tσ
ˆ
3 The SQCLP Programming Scheme
In this section we develop the SQCLP scheme with instances SQCLP(S, D, C) announced in the introduction. The parameters S, D and C stand for an admissible
proximity relation, a qualification domain and a constraint domain with a certain signature Σ, respectively. By convention, we consider only those instances of
the scheme whose parameters are chosen to constitute an admissible triple in the
sense of Definition 2.14. We focus on declarative semantics, using an interpretation
transformer and a logical inference system to provide alternative characterizations
of least program models. We also discuss declarative semantics of goals and related
approaches.
A brief remark regarding notation is in place here. For the sake of notational
consistency with previous works (either by us or other authors) where similarity
rather than proximity relations were used, we keep the symbol S for proximity
relations and the uppercase letter S in the names of programming schemes. Our
results, however, do not rely on the transitivity property from Definition 2.13.
3.1 Programs and their Declarative Semantics
A SQCLP(S, D, C)-program is a set P of qualified program rules (also called qualified
α
clauses) of the form C : A ←
− B1 ]w1 , . . . , Bm ]wm , where A is a defined atom, α ∈

26

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

DD \ {b} is called the attenuation factor of the clause and each Bj ]wj (1 ≤ j ≤ m)
is an atom Bj annotated with a so-called threshold value wj ∈ (DD \{b})]{?}. The
intended meaning of C is as follows: if for all 1 ≤ j ≤ m one has Bj ]ej (meaning
that Bj holds with qualification value ej ) for some ej Q? wj , then A]d (meaning
that A holds with qualification value d) can be inferred for any d ∈ D \ {b} such
dm
that d P α ◦ j=1 ej . By convention, ej Q? wj means ej Q wj if wj 6= ? and is
identically true otherwise. In practice threshold values equal to ‘?’ and attenuation
values equal to t can be omitted.
As motivating example, consider a SQCLP(S, U⊗W, R)-program P including
the clauses and equations for S displayed in Figure 1. From Subsection 2.2 recall that qualification values in U ⊗ W are pairs (d, e) (where d represents a certainty degree and e represents a proof cost), as well as the behavior of P and
◦ in U ⊗ W. Consider the problem of proving goodWork(king liar)](d, e) from
P. This can be achieved for d = 0.75 × min{d1 , d2 }, e = 3 + max{e1 , e2 } by
using R1 instantiated by {X 7→ king liar, Y 7→ shakespeare}, and going on
to prove famousAuthor(shakespeare)](d1 , e1 ) for some d1 ≥ 0.5, e1 ≤ 100 and
wrote(shakespeare,king liar)](d2 , e2 ) for some d2 , e2 . Thanks to R2 , R3 and
S, these proofs succeed with (d1 , e1 ) = (0.9, 1) and (d2 , e2 ) = (0.8, 2). Therefore,
the desired proof succeeds with certainty degree d = 0.75 × min{0.9, 0.8} = 0.6,
and proof cost e = 3 + max{1, 2} = 5.

R1 : goodWork(X) <-(0.75,3)- famousAuthor(Y)#(0.5,100), wrote(Y,X)#?
R2 : famousAuthor(shakespeare) <-(0.9,1)R3 : wrote(shakespeare,king_lear) <-(1,1)S(king_lear,king_liar) = (0.8,2)

Fig. 1. SQCLP(S, U ⊗W, R) Program Fragment

It is useful to define some special types of program clauses and programs, as
follows:
• A clause is called attenuation-free iff α = t. The name is justified because t is
an identity element for the attenuation operator ◦, as explained in Subsection
2.2. By convention, attenuation-free clauses may be written with the simplified
syntax A ← B1 ]w1 , . . . , Bm ]wm .
• A clause is called threshold-free iff wj = ? for all j = 1 . . . m. The name
is justified because the threshold value wj = ? occurring as annotation of a
body atom Bj does not impose any particular requirement to the qualification
value of Bj . Threshold-free clauses may be written with the simplified syntax
α
A←
− B1 , . . . , B m .
• A clause is called qualification-free iff it is both attenuation-free and thresholdfree. These clauses may be written with the simplified syntax A ← B1 , . . . , Bm .
They behave just like those used in the classical CLP scheme.
• A clause is called constraint-free iff all its body atoms are defined.

Fixpoint & Proof-theoretic Semantics for SQCLP

27

• A program is called attenuation-free iff all its clauses are of this type. Threshold-free, qualification-free and constraint-free programs are defined similarly.
The more technical SQCLP(S, U, R)-program P presented below will serve as a
running example to illustrate various points in the rest of the report.
Example 3.1 (Running example)
Assume unary constructors c, c0 ∈ DC 1 , binary predicate symbols p, p0 , q ∈ DP 2
and a ternary predicate symbol r ∈ DP 3 . Consider the admissible triple hS, U, Ri,
where S is an U-valued proximity relation such that S(c, c0 ) = 0.9 and S(p, p0 ) = 0.8.
Let P be the SQCLP(S, U, R)-program consisting of the qualified clauses R1 , R2
and R3 listed below:
1.0

R1 : q(X, c(X)) ←−−
0.9

R2 : p(c(X), Y ) ←−− q(X, Y )]0.8
0.9

R3 : r(c(X), Y, Z) ←−− q(X, Y )]0.8, cp≥ (X, 0.0)]?

As we will see in the Conclusions, the classical CLP scheme for Constraint Logic
Programming originally introduced in (Jaffar and Lassez 1987) can be seen as a
particular case of the SQCLP scheme. In the rest of this subsection we present
a declarative semantics for SQCLP(S, D, C)-programs inspired by (Gabbrielli and
Levi 1991; Gabbrielli et al. 1995). These papers provided three different program
semantics Si (i = 1, 2, 3) characterizing valid ground solutions for goals, valid open
solutions for goals and computed answers for goals in CLP, respectively. In fact, the
Si semantics in (Gabbrielli and Levi 1991; Gabbrielli et al. 1995) were conceived
as the CLP counterpart of previously known semantics for logic programming,
namely the least ground Herbrand model semantics (Apt 1990; Lloyd 1987), the
open Herbrand model semantics, also known as C-semantics (Clark 1979; Falaschi
et al. 1993), and the S-semantics (Falaschi et al. 1989; Bossi et al. 1994); see (Apt
and Gabbrielli 1994) for a very concise and readable overview.
In this report we restrict ourselves to develop a S2 -like semantics which can
be used to characterize valid open solutions for SQCLP goals as we will see in
Subsection 3.2. As a basis for our semantics we use so-called qc-atoms of the form
A]d ⇐ Π, intended to assert that the atom A is entailed by the constraint set
Π with qualification degree d. We also use a special entailment relation <D,C
intended to capture some implications between qc-atoms whose validity depends
neither on the proximity relation S nor on the semantics of defined predicates. A
formal definition of these notions is as follows:
Definition 3.1 (qc-atoms, observables and (D, C)-entailment)
1. Qualified constrained atoms (or simply qc-atoms) are statements of the form
A]d ⇐ Π, where A ∈ At(Σ, B, Var) is an atom, d ∈ D is a qualification value,
and Π ⊆ ConC is a finite set of constraints.
2. A qc-atom A]d ⇐ Π is called defined, primitive or equational according to the
syntactic form of A.
3. A qc-atom A]d ⇐ Π is called observable iff d ∈ D \ {b} and Π is satisfiable.

28

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az
4. Given two qc-atoms ϕ : A]d ⇐ Π and ϕ0 : A0 ]d0 ⇐ Π0 , we say that ϕ (D, C)entails ϕ0 (in symbols, ϕ <D,C ϕ0 ) iff there is some C-substitution θ satisfying
A0 = Aθ, d0 P d and Π0 |=C Πθ.

We will focus our attention on observable qc-atoms because they can be interpreted as observations of valid open solutions for atomic goals in SQCLP(S, D, C)
as we will see in Subsection 3.2. The example below illustrates the main technical
ideas from Definition 3.1.
Example 3.2 (Observable qc-atoms and (D, C)-entailment)
Consider the admissible triple underlying Example 3.1 and the sets of R-constraints:
Π = {cp> (X, 1.0), op+ (A, A, X), op× (2.0, A, Y )}
Π0 = {cp≥ (A, 3.0), op× (2.0, A, X), op+ (A, A, Y )}
Then, the following are observable qc-atoms:
ϕ1 = q(X, c0 (Y ))]0.9 ⇐ Π
ϕ2 = p0 (c0 (Y ), c(X))]0.8 ⇐ Π

ϕ3 = r(c0 (Y ), c(X), Z)]0.8 ⇐ Π
ϕ03 = r(c0 (Y ), c(X), c(Z 0 ))]0.7 ⇐ Π0

and the (U, R)-entailment ϕ3 <U ,R ϕ03 is valid thanks to θ = {Z 7→ c(Z 0 )}, which
satisfies r(c0 (Y ), c(X), c(Z 0 )) = r(c0 (Y ), c(X), Z)θ, 0.7 ≤ 0.8 and Π0 |=R Πθ.
The intended meaning of <D,C as an entailment relation not depending on the
meanings of defined predicates motivates the first item in the next definition.
Definition 3.2 (Interpretations)
Let hS, D, Ci be any given admissible triple. Then:
1. A qualified constrained interpretation (or qc-interpretation) is a set I of observable defined qc-atoms closed under (D, C)-entailment. In other words, a
set I of qc-atoms which satisfies the following two conditions:
(a) Each ϕ ∈ I is an observable defined qc-atom.
(b) If ϕ ∈ I and ϕ0 is another defined observable qc-atom such that
ϕ <D,C ϕ0 , then also ϕ0 ∈ I.
2. Assume any given qc-interpretation I. For any observable qc-atom ϕ, we say
that ϕ is valid in I modulo S (in symbols, I ``S,D,C ϕ) iff some of the three
cases below holds:
(a) ϕ is defined and ϕ ∈ I.
(b) ϕ : (t == s)]d ⇐ Π is equational and t ≈d,Π s.
(c) ϕ : κ]d ⇐ Π is primitive and Π |=C κ.
Note that a given interpretation I can include several observables A]di ⇐ Π for
the same (possibly not ground) atom A but is not required to include on “optimal”
observable A]d ⇐ Π with d computed as the lub of all di . By contrast, the other
related works discussed in the Introduction view program interpretations as mappings I from the ground Herbrand base into some set of lattice elements (the real
interval [0, 1] in many cases). In such interpretations, each ground atom A has attached one single lattice element d = I(A) intended as “the optimal qualification”

Fixpoint & Proof-theoretic Semantics for SQCLP

29

for A. Our view of interpretations is closer to the expected operational behavior
of goal solving systems and can be used to characterize the validity of solutions
computed by such systems, as we will see in Subsection 3.2.
Note also that the notation I ``S,D,C ϕ is defined only for the case that ϕ is
observable. In the sequel, we will implicitly assume that ϕ is observable in any
context where the notation I ``S,D,C ϕ is used. The next technical result shows
that validity in any given interpretation is closed under entailment.
Proposition 3.1 (Entailment Property for Interpretations)
Assume that I ``S,D,C ϕ and ϕ <D,C ϕ0 . Then I ``S,D,C ϕ0 .
Proof
Due to the hypothesis ϕ <D,C ϕ0 we can assume ϕ = (A]d ⇐ Π), ϕ0 = (A0 ]d0 ⇐ Π0 )
and some C-substitution θ such that A0 = Aθ, d0 P d and Π0 |=C Πθ. We now
distinguish cases according to the syntactic form of ϕ:
1. ϕ is defined. In this case, ϕ0 is also defined. Moreover, I ``S,D,C ϕ is equivalent to
ϕ ∈ I because of Definition 3.2, which implies ϕ0 ∈ I because qc-interpretations
are closed under <D,C , which is equivalent to I ``S,D,C ϕ0 because of Definition
3.2.
2. ϕ is equational. In this case A and A0 have the form t == s and tθ == sθ, respectively. Moreover, I ``S,D,C ϕ is equivalent to t ≈d,Π s because of Definition 3.2,
which implies tθ ≈d,Πθ sθ because of Lemma 2.8, which trivially implies tθ ≈d0 ,Π0 sθ
because of Π0 |=C Πθ and d0 P d, which is equivalent to I ``S,D,C ϕ0 because of
Definition 3.2.
3. ϕ is primitive. In this case A and A0 have the form κ and κθ, respectively. Moreover, I ``S,D,C ϕ is equivalent to Π |=C κ because of Definition 3.2, which implies
Πθ |=C κθ because of Lemma 2.1, which implies Π0 |=C κθ because of Π0 |=C Πθ,
which is equivalent to I ``S,D,C ϕ0 because of Definition 3.2.
The definition below explains when a given interpretation is regarded as a model
of a given program, as well as the related notion of semantic consequence.
Definition 3.3 (Models and semantic consequence)
Let a SQCLP(S, D, C)-program P and an observable qc-atom ϕ : p0 (t0 n )]d ⇐ Π
be given. ϕ is an immediate consequence of a qc-interpretation I via a program
α
rule (Rl : p(tn ) ←
− B1 ]w1 , . . . , Bm ]wm ) ∈ P iff there exist a C-substitution θ and a
choice of qualification values d0 , d1 , . . . , dn , e1 , . . . , em ∈ D \ {b} such that:
(a)
(b)
(c)
(d)

S(p0 , p) = d0
I ``S,D,C (t0i == ti θ)]di ⇐ Π (i.e. t0i ≈di ,Π ti θ) for i = 1 . . . n
I ``S,D,C Bj θ]ej ⇐ Π with ej Q? wj for j = 1 . . . m
dn
dm
d P i=0 di u α ◦ j=1 ej [i.e., d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤ j ≤ m)]

Note that the qualification value d attached to ϕ is limited by two kinds of upper
bounds: di (0 ≤ i ≤ n), i.e. the S-proximity between p0 (t0 n ) and the head of
Rl θ; and α ◦ ej (1 ≤ j ≤ m), i.e. the qualification values of the atoms in the
body of Rl θ attenuated w.r.t. Rl ’s attenuation factor α. Moreover, the inequalities

30

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

ej Q? wj (1 ≤ j ≤ m) are required in order to impose the threshold conditions
within Rl ’s body. As already explained at the beginning of this subsection, ej Q?wj
means that either wj = ? or else wj ∈ D \ {b} and ej Q wj . Now we can define:

1. I is a model of a program rule Rl ∈ P (in symbols, I |=S,D,C Rl ) iff every
defined observable qc-atom ϕ which is an immediate consequence of I via Rl
verifies ϕ ∈ I; and I is a model of P (in symbols, I |=S,D,C P) iff I is a model
of every program rule Rl ∈ P.
2. ϕ is a semantic consequence of P (in symbols, P |=S,D,C ϕ) iff I ``S,D,C ϕ for
every qc-interpretation I such that I |=S,D,C P.

The next example may serve as a concrete illustration:
Example 3.3 (Models and semantic consequence)
Recall the SQCLP(S, U, R)-program P from Example 3.1. Let us show that the
three qc-atoms ϕ1 , ϕ2 and ϕ3 from Example 3.2 are semantic consequences of P:
1. Assume an arbitrary model I |=S,U ,R P. Note that the atom underlying ϕ1
and the head atom of R1 are q(X, c0 (Y )) and q(X, c(X)), respectively. Since
S(c, c0 ) = 0.9 and Π |=C X == Y , ϕ1 can be obtained as an immediate
consequence of I via R1 using θ = ε. Therefore ϕ1 ∈ I and we can conclude
that P |=S,U ,R ϕ1 .
2. Assume an arbitrary model I |=S,U ,R P. Consider the substitution θ = {Y 7→
c0 (Y )}. Note that the atom underlying ϕ2 and the head atom of R2 θ are
p0 (c0 (Y ), c(X)) and p(c(X), c0 (Y )), respectively. Moreover, ϕ1 ∈ I (due to the
previous item) and the atom q(X, c0 (Y )) underlying ϕ1 is the same as the atom
in the body of R2 θ. These facts together with S(p, p0 ) = 0.8, S(c, c0 ) = 0.9
and Π |=C X == Y allow to obtain ϕ2 as an immediate consequence of I via
R2 . Therefore ϕ2 ∈ I and we can conclude that P |=S,U ,R ϕ2 .
3. Assume an arbitrary model I |=S,U ,R P. Consider again the substitution
θ = {Y 7→ c0 (Y )}. Note that the atom underlying ϕ3 and the head atom of
R3 θ are r(c0 (Y ), c(X), Z) and r(c(X), c0 (Y ), Z), respectively. Moreover, the
two annotated atoms Bj θ]wj (1 ≤ j ≤ 2) occurring in the body of R3 θ
are such that I ``S,D,C Bj θ]ej ⇐ Π for suitable values ej ≥? wj , namely
e1 = 0.9 and e2 = 1.0. Note that e1 = 0.9 works because B1 θ is the atom
q(X, c0 (Y )) underlying ϕ1 and ϕ1 ∈ I, as proved in the first item of this
example. On the other hand, e2 = 1.0 works because B2 θ is the primitive
atom cp≥ (X, 0.0) which is trivially entailed by Π. All these facts, together
with S(c, c0 ) = 0.9, 0.8 ≤ 0.9 × 0.9 and Π |=C X == Y allow to obtain ϕ3 as
an immediate consequence of I via R3 . Therefore ϕ3 ∈ I and we can conclude
that P |=S,U ,R ϕ3 .
Now we are ready to obtain results on the declarative semantics of programs in
the SQCLP scheme. We will characterize the observable consequences of a given
program P in two different, but equivalent, ways: either using the interpretation
transformer presented in Subsection 3.1.1, or using the extension of Horn Logic
presented in Subsection 3.1.2. In both approaches, we will prove the existence of a
least model MP for each given program P.

Fixpoint & Proof-theoretic Semantics for SQCLP

31

3.1.1 A Fixpoint Semantics
A well-known way of characterizing models and least models of programs in declarative languages proceeds by considering a lattice structure for the family of all
program interpretations, and using an interpretation transformer to compute the
immediate consequences obtained from program rules. This kind of approach is
well known for logic programming (van Emden and Kowalski 1976; Apt and van
Emden 1982; Lloyd 1987; Apt 1990) and constraint logic programming (Gabbrielli
and Levi 1991; Gabbrielli et al. 1995; Jaffar et al. 1998). It has been used also in
various extensions of logic programming designed to support uncertain reasoning,
such as quantitative logic programming (van Emden 1986), its extension to qualified logic programming (Rodrı́guez-Artalejo and Romero-Dı́az 2008b) quantitative
constraint logic programming (Riezler 1996; Riezler 1998), similarity-based logic
programming (Sessa 2002) and proximity-based logic programming in the sense of
Bousi∼Prolog (Julián-Iranzo and Rubio-Manzano 2009a).
The SQCLP scheme is intended to unify all these logic programming extensions
in a common framework. This subsection is based on the declarative semantics given
in (Rodrı́guez-Artalejo and Romero-Dı́az 2008b; Rodrı́guez-Artalejo and RomeroDı́az 2008a), extended to deal with constraints and proximity relations. Our first
result provides a lattice of program interpretations.
Proposition 3.2 (Lattice of Interpretations)
IntD,C , defined as the set of all qc-interpretations over the qualification domain D
and the constraint domain C, is a complete lattice w.r.t. the set inclusion ordering
⊆. Moreover, the bottom element ⊥⊥ and the top element >> of this lattice are
characterized as ⊥
⊥ = ∅ and >
> = {ϕ | ϕ is a defined observable qc-atom} and for
any subset I ⊆ IntD,C its greatest lower bound (glb) and least upper bound (lub)
are characterized as follows:
d
T
1. The glb of I (written as I) is I∈I I, understood as >> if I = ∅; and
F
S
2. The lub of I (written as I) is I∈I I, understood as ⊥⊥ if I = ∅.
Proof
Both ⊥
⊥ and >
> are qc-interpretations because they are sets of defined observable
qc-atoms and they are closed under (D, C)-entailment for trivial reasons, namely:
⊥
⊥ is empty and >
> includes all the defined observables. Moreover, they are the
minimum and the maximum of IntD,C w.r.t. ⊆ because ⊥⊥ ⊆ I ⊆ >> is trivially
true for each I ∈ IntD,C . Thus, we have only left to prove 1. and 2.:
T
1. I∈I I is obviously a set of defined observable qc-atoms because this is the case
T
for each I ∈ I. Given any ϕ ∈ I∈I and any observable defined qc-atom ϕ0 such
T
that ϕ <D,C ϕ0 , we get ϕ0 ∈ I∈I I as an obvious consequence of the fact that each
T
I ∈ I is closed under (D, C)-entailment. Therefore, I∈I I ∈ IntD,C . Obviously,
T
T
I∈I I is trivially a lower bound of I w.r.t. ⊆. Moreover,
I∈I I is the glb of I,
because any given lower bound J of I verifies J ⊆ I for every I ∈ I and thus
T
T
d
J ⊆ I∈I I. Therefore, I∈I I = I.

32

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

S
2. Using the properties of the union of a family of sets it is easy to prove that I∈I I ∈
S
IntD,C and also that I∈I I is the lub of I w.r.t. ⊆. A more detailed reasoning would
S
F
be similar to the previous item. Therefore, I∈I I = I.
Next we define an interpretation transformer TP , intended to compute the immediate consequences obtained from a given qc-interpretation via the program rules
belonging to P.
Definition 3.4 (Interpretations Transformer )
Let P be a fixed SQCLP(S, D, C)-program. The interpretations transformer TP :
IntD,C → IntD,C is defined by the condition:
TP (I) =def {ϕ | ϕ is an immediate consequence of I via some Rl ∈ P} .
The computation of immediate consequences of a given qc-interpretation I via a
given program rule Rl has been already explained in Definition 3.3. The following
example illustrates the workings of TP .
Example 3.4 (Interpretation transformer in action)
Recall again the SQCLP(S, U, R)-program P from Example 3.1 and the observable
defined qc-atoms ϕ1 , ϕ2 and ϕ3 from Example 3.2. Then:
1. The arguments given in Example 3.3(1) can be easily reused to show that ϕ1
is an immediate consequence of the empty interpretation ⊥⊥ via the program
rule R1 . Therefore, ϕ1 ∈ TP (⊥⊥).
2. The arguments given in Example 3.3(2) can be easily reused to show that
ϕ1 is an immediate consequence of I via the program rule R2 , provided that
ϕ1 ∈ I. Therefore, ϕ2 ∈ TP (TP (⊥⊥)).
3. The arguments given in Example 3.3(3) can be easily reused to show that
ϕ3 is an immediate consequence of I via the program rule R3 , provided that
ϕ1 ∈ I. Therefore, ϕ3 ∈ TP (TP (⊥⊥)).
The next proposition states the main properties of interpretation transformers.
Proposition 3.3 (Properties of interpretation transformers)
Let P be any fixed SQCLP(S, D, C)-program. Then:
1. TP is a well defined mapping, i.e. for all I ∈ IntD,C one has TP (I) ∈ IntD,C .
2. TP is monotonic and continuous.
3. For all I ∈ IntD,C one has: I |=S,D,C P ⇐⇒ TP (I) ⊆ I, That is, the models
of P are precisely the pre-fixpoints of TP .
Proof
1. By definition, TP (I) is a set of observable defined qc-atoms. It is sufficient to prove
that it is closed under (D, C)-entailment. Let us assume two observable defined qcatoms ϕ and ϕ0 such that ϕ ∈ TP (I) and ϕ <D,C ϕ0 . Because of ϕ <D,C ϕ0 we can
assume ϕ : p(tn )]d ⇐ Π, ϕ0 : p(t0 n )]d0 ⇐ Π0 and some substitution θ such that
p(t0 n ) = p(tn )θ, d0 P d and Π0 |=C Πθ. Because of ϕ ∈ TP (I), we can assume that ϕ
is an immediate consequence of I via some Rl ∈ P. More precisely, we can assume
α
(Rl : q(sn ) ←
− B1 ]w1 , . . . , Bm ]wm ) ∈ P, some substitution σ and some qualification
values d0 , d1 , . . . , dn , e1 , . . . , em ∈ D \ {b} such that

Fixpoint & Proof-theoretic Semantics for SQCLP
(a)
(b)
(c)
(d)

33

S(p, q) = d0 ,
I ``S,D,C (ti == si σ)]di ⇐ Π for i = 1 . . . n,
I ``S,D,C Bj σ]ej ⇐ Π with ej Q? wj for j = 1 . . . m,
dn
dm
d P i=0 di u α ◦ j=1 ej [i.e., d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤ j ≤ m)].

In order to show that ϕ0 ∈ TP (I), we claim that ϕ0 can be computed as an immediate consequence of I via the same program rule Rl , using the substitution σθ and
the qualification values d0 , d1 , . . . , dn , e1 , . . . , em ∈ D \ {b}. To justify this claim it
is enough to check the following items:
(a’)
(b’)
(c’)
(d’)

S(p, q) = d0 ,
I ``S,D,C (t0i == si σθ)]di ⇐ Π0 for i = 1 . . . n,
I ``S,D,C Bj σθ]ej ⇐ Π0 with ej Q? wj for j = 1 . . . m,
dn
dm
d P i=0 di u α ◦ j=1 ej [i.e., d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤ j ≤ m)].

These four items closely correspond to items (a)-(d) above. More specifically:
— Items (a’) and (d’) are identical to items (a) and (d), respectively.
— Regarding item (b’): For i = 1 . . . n, I ``S,D,C (t0i == si σθ)]di ⇐ Π is the same
as ti θ ≈di ,Π0 si σθ. Because of Lemma 2.8, this is a consequence of Π0 |=C Πθ and
ti ≈di ,Π si σ, which is ensured by item (b).
— Regarding item (c’): For j = 1 . . . m, ej Q? wj is ensured by item (c), and
I ``S,D,C Bj σθ]ej ⇐ Π0 follows from I ``S,D,C Bj σ]ej ⇐ Π –also ensured by item
(c)– and the entailment property for interpretations (Proposition 3.1), which can
be applied because Bj σ]ej ⇐ Π <D,C Bj σθ]ej ⇐ Π0 .
2. Monotonicity means that the inclusion TP (I) ⊆ TP (J ) holds whenever I ⊆ J .
This follows very easily from
(♠) I ``S,D,C ϕ and I ⊆ J =⇒ J ``S,D,C ϕ
which is a trivial consequence of Definition 3.2.
F
F
Continuity means that the equation TP ( I) = {TP (I) | I ∈ I} holds for any
directed set I ⊆ IntD,C of qc-interpretations. Recall that I ⊆ IntD,C is called directed iff every finite subset I0 ⊆ I has some upper bound I ∈ I. We show that
F
F
TP ( I) = {T p(I) | I ∈ I} holds by proving the two inclusions separately:
F
F
(a) For each fixed I0 ∈ I, TP (I0 ) ⊆ TP ( I) follows from I0 ⊆ I and monoF
F
tonicity of TP . Then, the inclusion {TP (I) | I ∈ I} ⊆ TP ( I) holds by
definition of supremum.
F
F
(b) In order to prove the opposite inclusion TP ( I) ⊆ {TP (I) | I ∈ I}, conF
sider an arbitrary ϕ ∈ TP ( I). Due to Definition 3.4, ϕ is an immediate
F
consequence of I via some program rule Rl ∈ P. Because of the first item
F
of Definition 3.3, ϕ is an immediate consequence of I via Rl due to finitely
many qc-facts of the form Bj θ]ej ⇐ Π (coming from the body of a suitable
F
instance of Rl ) that are valid in I. Because of (♠) and the assumption that
I is a directed set, it is possible to choose some I0 ∈ I such that all the
qc-facts Bj θ]ej ⇐ Π are valid in I0 . Then, ϕ is an immediate consequence of
F
this particular I0 ∈ I via Rl . Therefore, ϕ ∈ TP (I0 ) ⊆ {TP (I) | I ∈ I}.

34

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

3. According to Definition 3.3, I |=S,D,C P holds iff every observable defined qc-atom
ϕ which is an immediate consequence of I via the program rules Rl ∈ P verifies
ϕ ∈ I. According to Definition 3.4, TP (I) is just the set of all the defined observable
qc-atoms ϕ that can be obtained as immediate consequences of I via the program
rules Rl ∈ P. Consequently, I |=S,D,C P holds iff TP (I) ⊆ I.
The theorem below is the main result in this subsection.
Theorem 3.1 (Fixpoint characterization of least program models)
Every SQCLP(S, D, C)-program P has a least model MP , smaller than any other
model of P w.r.t. the set inclusion ordering of the interpretation lattice IntD,C .
Moreover, MP can be characterized as the least fixpoint of TP as follows:
[
MP = lfp(TP ) =
TP ↑k (⊥⊥) .
k∈N

Proof
As usual, a given I ∈ IntD,C is called a fixpoint of TP iff TP (I) = I, and I is
called a pre-fixpoint of TP iff TP (I) ⊆ I. Due to a well-known theorem by Knaster
and Tarski, see (Tarski 1955), a monotonic mapping from a complete lattice into
itself always has a least fixpoint which is also its least pre-fixpoint. In the case that
the mapping is continuous, its least fixpoint can be characterized as the lub of the
sequence of lattice elements obtained by reiterated application of the mapping to
the bottom element. Combining these results with Proposition 3.3 trivially proves
the theorem.
3.1.2 An equivalent Proof-theoretic Semantics
In order to give a logical view of program semantics and an alternative characterization of least program models, we define the Proximity-based Qualified Constrained
Horn Logic SQCHL(S, D, C) as a formal inference system consisting of the three
inference rules displayed in Figure 2.

SQDA

( (t0i == ti θ)]di ⇐ Π )i=1...n ( Bj θ]ej ⇐ Π )j=1...m
p0 (t0 n )]d ⇐ Π
α

if (p(tn ) ←
− B1 ]w1 , . . . , Bm ]wm ) ∈ P, θ subst., S(p0 , p) = d0 6= b,
d
dm
ej Q? wj (1 ≤ j ≤ m) and d P n
i=0 di u α ◦
j=1 ej .
SQEA
SQPA

(t == s)]d ⇐ Π
κ]d ⇐ Π

if t ≈d,Π s.

if Π |=C κ.

Fig. 2. Proximity-based Qualified Constrained Horn Logic

Fixpoint & Proof-theoretic Semantics for SQCLP

35

The three inference rules are intended to work with observable qc-atoms. Rule
SQDA is used to infer defined qc-atoms. It formalizes an extension of the classical
Modus Ponens inference, allowing to infer a defined qc-atom p0 (t0 n )]d ⇐ Π by
means of an instance of a program clause with head p(tn )θ and body atoms Bj θ]wj .
The n premises (t0i == ti θ)]di ⇐ Π combined with the side condition S(p0 , p) =
d0 6= b ensure the “equality” between p0 (t0 n ) and p(tn )θ modulo S; the m premises
Bj θ]ej ⇐ Π require to prove the body atoms; and the side conditions ej Q? wj
dn
dm
and d P i=0 di u α ◦ j=1 ej check the threshold conditions of the body atoms
and impose the proper relationships between the qualification value attached to the
conclusion and the qualification values attached to the premises. In particular, the
dm
inequality d P α◦ j=1 ej is imposed, meaning that the qualification value attached
to a clause’s head cannot exceed the glb of the qualification values attached to the
body atoms attenuated by the clause’s attenuation factor. Rules SQEA and SQPA
are used to infer equational and primitive qc-atoms, respectively. Rule SQEA is
designed to work with term proximity w.r.t. Π in the sense of Definition 2.16,
inferring (t == s)]d ⇐ Π just in the case that t ≈d,Π s holds. Rule SQPA infers
κ]d ⇐ Π for an arbitrary d ∈ D \ {b}, provided that Π |=C κ holds. This makes
sense because the requirements for admissible triples in Definition 2.14 include the
assumption that S(p, p0 ) 6= b cannot happen if p, p0 ∈ P P are syntactically different
primitive predicate symbols.
As usual in formal inference systems, SQCHL(S, D, C) proofs can be represented
as proof trees T whose nodes correspond to qc-atoms, each node being inferred
from its children by means of some SQCHL(S, D, C) inference step. In the rest of
the report we will use the following notations:
• kT k will denote the size of the proof tree T , measured as its number of nodes,
which equals the number of inference steps in the SQCHL(S, D, C) proof represented by T .
• kT kd will denote the number of nodes of the proof tree T that represent
conclusions of SQDA inference steps. Obviously, kT kd ≤ kT k.
• P `S,D,C ϕ will indicate that ϕ can be inferred from P in SQCHL(S, D, C).
• P `kS,D,C ϕ will indicate that ϕ can be inferred from P in SQCHL(S, D, C)
using some proof tree T such that kT kd = k.
The next example shows a SQCHL(S, U, R) proof tree.
Example 3.5 (SQCHL(S, D, C) proof tree)
Recall the proximity relation S and the program P from our running Example 3.1,
as well as the observable qc-statement ϕ2 = p0 (c0 (Y ), c(X))]0.8 ⇐ Π already known
from Example 3.2. A SQCHL(S, U, R) proof tree witnessing P `S,U ,R ϕ2 can be
displayed as follows:
(5)
(6)
(Y == Y )]1.0 ⇐ Π
(c(X) == c(Y ))]1.0 ⇐ Π
♠=
(4)
q(Y, c(X))]1.0 ⇐ Π

36

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

(2)
(3)
(c0 (Y ) == c(Y ))]0.8 ⇐ Π
(c(X) == c(X))]1.0 ⇐ Π
p0 (c0 (Y ), c(X))]0.8 ⇐ Π

♠ (4)
(1)

The inference steps in this proof are commented below. For the sake of clarity,
we have used a different variant of the corresponding program clause for each each
application of the inference rule SQDA.
0.9

(1) SQDA step with clause R1 = ( p(c(X1 ), Y1 ) ←−− q(X1 , Y1 ) ) instantiated
by substitution θ1 = {X1 7→ Y, Y1 7→ c(X)}. Note that 0.8 satisfies 0.8 ≤
S(p, p0 ) = 0.8, 0.8 ≤ 0.8, 0.8 ≤ 1.0, 0.8 ≤ 0.9 × 1.0.
(2) SQEA step. c0 (Y ) ≈0.8,Π c(Y ) holds due to c0 (Y ) ≈Π c0 (Y ), c(Y ) ≈Π c(Y )
and c0 (Y ) ≈0.8 c(Y ).
(3) SQEA step. c(X) ≈1.0,Π c(X) holds for trivial reasons.
1.0

(4) SQDA step with clause R2 = ( q(X2 , c(X2 )) ←−− ) instantiated by substitution θ2 = {X2 7→ Y }. Note that 1.0 satisfies 1.0 ≤ S(q, q) = 1.0 and
1.0 ≤ 1.0.
(5) SQEA step. Y ≈1.0,Π Y holds for trivial reasons.
(6) SQEA step. c(X) ≈1.0,Π c(Y ) holds due to c(X) ≈Π c(Y ) (which follows
from Π |=R X == Y ) and c(X) ≈1.0 c(X).
The next technical lemma establishes two basic properties of formal inference in
the SQCHL(S, D, C) logic.
Lemma 3.1 (Properties of SQCHL(S, D, C) derivability)
Let P be any SQCLP(S, D, C)-program. Then:
1. P-independent Inferences:
Given any C-based qc-atom ϕ and any qc-interpretation I, one has:
P `0S,D,C ϕ ⇐⇒ P `S,D,C ϕ ⇐⇒ I ``S,D,C ϕ .
2. Entailment Property for Programs:
Given any pair of qc-atoms ϕ and ϕ0 such that P `S,D,C ϕ with inference
proof tree T and ϕ <D,C ϕ0 , then P `S,D,C ϕ0 with an inference proof tree T 0
of the same size and structure as T .
Proof of P-independent Inferences
Since ϕ is C-based, we can assume ϕ = A]d ⇐ Π where A is either an equation or a
primitive atom. In both cases the equivalence P `0S,D,C ϕ ⇐⇒ P `S,D,C ϕ is obvious.
In order to prove the equivalence P `S,D,C ϕ ⇐⇒ I ``S,D,C ϕ we distinguish the
two cases:
1. ϕ is equational. Then A has the form t == s. Considering the SQCHL(S, D, C)inference rule SQEA and the second item of Definition 3.2, we get
P `S,D,C ϕ ⇐⇒ s ≈d,Π t ⇐⇒ I ``S,D,C ϕ .

Fixpoint & Proof-theoretic Semantics for SQCLP

37

2. ϕ is primitive. Then A is a primitive atom κ. Considering the SQCHL(S, D, C)inference rule SQPA and the second item of Definition 3.2, we get
P `S,D,C ϕ ⇐⇒ Π |=C κ ⇐⇒ I ``S,D,C ϕ .
Proof of Entailment Property for Programs
Due to the hypothesis ϕ <D,C ϕ0 and Definition 3.1, we can assume ϕ = A]d ⇐ Π
and ϕ0 = A0 ]d0 ⇐ Π0 with A0 = Aθ, d0 P d and Π0 |=C Πθ for some substitution θ.
We reason by complete induction on kT k. There are three possible cases, according
to the the syntactic form of the atom A. In each case we argue how to build the
desired proof tree T 0 .
1. A is a defined atom: In this case, A is p(tn ) with p ∈ DP n , and A0 : is p(t0 n ) with
p(t0 n ) = p(tn )θ. Moreover, T must be a proof tree of the following form:




···
(ti == si σ)]di ⇐ Π i=1...n
Bj σ]ej ⇐ Π j=1...m
T :
SQDA
p(tn )]d ⇐ Π
where:
α

− B1 ]w1 , . . . , Bm ]wm ) ∈ P,
• The SQDA root inference uses some Rl : (q(sn ) ←
some substitution σ and some qualification values d0 , d1 , . . . , dn , e1 , . . . em ∈
D \ {b} such that S(p, q) = d0 6= b, d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤
j ≤ m).
• For i = 1 . . . n, (ti == si σ)]di ⇐ Π has a proof tree Tih with kTih k < kT k.
• For j = 1 . . . m, Bj σ]ej ⇐ Π has a proof tree Tjb with kTjb k < kT k.
Then, T 0 can be built as a proof tree of the form:



T0 :

(t0i == si σθ)]di ⇐ Π0

i=1...n

···
Bj σθ]ej ⇐ Π0

p(t0 n )]d0 ⇐ Π0


j=1...m

SQDA

where:
• The SQDA root inference uses the same program clause Rl ∈ P, the substitution σθ and the same qualification values di (0 ≤ i ≤ n) and ej (1 ≤ j ≤ m),
satisfying S(p, q) = d0 6= b, d0 P d P di (0 ≤ i ≤ n) and d0 P d P α ◦ ej (1 ≤
j ≤ m).
0
• For i = 1 . . . n, (t0i == si σθ)]di ⇐ Π0 has a proof tree Ti h of the same size
0
and structure as Tih . In fact, Ti h can be obtained by induction hypothesis
applied to Tih , which is allowed because kTih k < kT k and (ti == si σ)]di ⇐
Π <D,C (t0i == si σθ)]di ⇐ Π0 . Note that this entailment holds thanks to
substitution θ, since t0i = ti θ and Π0 |=C Πθ.
0
• For j = 1 . . . m, Bj σθ]ej ⇐ Π0 has a proof tree Tj b of the same size and
0
structure as Tjb . In fact, Tj b can be obtained by induction hypothesis applied
to Tjb , which is allowed because kTjb k < kT k and Bj σ]ej ⇐ Π <D,C Bj σθ]ej ⇐
Π0 . Note that this entailment holds thanks to substitution θ, since Π0 |=C Πθ.

38

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

By construction, T 0 has the same size and structure as T , as desired.
2. A is an equation: In this case, A : t == s and A0 : t0 == s0 with t0 = tθ, s0 = sθ.
Moreover, T must consist of one single node (t == s)]d ⇐ Π inferred by means of
SQEA. Therefore, t ≈d,Π s holds. This implies tθ ≈d,Πθ sθ (i.e. t0 ≈d,Πθ s0 ) due
to the Substitution Lemma 2.8. From this we conclude t0 ≈Π0 s0 due to d0 P d and
Π0 |=C Πθ. Therefore, T 0 can be built as a proof tree consisting of one single node
(t0 == s0 )]d0 ⇐ Π0 inferred by means of SQEA.
3. A is a primitive atom: In this case, A : κ and A0 : κ0 = κθ. Moreover, T must consist
of one single node κ]d ⇐ Π inferred by means of SQPA. Therefore, Π |=C κ holds.
This implies Πθ |=C κθ due to the Substitution Lemma 2.1. From this we conclude
Π0 |=C κ0 due to κ0 = κθ and Π0 |=C Πθ. Therefore, T 0 can be built as a proof tree
consisting of one single node κ0 ]d0 ⇐ Π0 inferred by means of SQPA.
The following theorem is the main result in this subsection. It characterizes the
least model of a SQCLP(S, D, C)-program P w.r.t. the logic SQCHL(S, D, C):
Theorem 3.2 (Logical characterization of least program models)
For any SQCLP(S, D, C)-program P, its least model can be characterized as:
MP = {ϕ | ϕ is a defined observable qc-atom and P `S,D,C ϕ} .
Proof
S
By Theorem 3.1, we already know that MP = k∈N TP ↑k (⊥⊥). Therefore, it is
sufficient to prove that the two implications
0

1. P `kS,D,C ϕ =⇒ ∃k 0 : ϕ ∈ TP ↑k (⊥⊥)
0

2. ϕ ∈ TP ↑k (⊥
⊥) =⇒ ∃k 0 : P `kS,D,C ϕ
hold for any defined observable qc-atom ϕ = p(tn )]d ⇐ Π and for any integer value
k ≥ 1. We prove both implications within one single inductive reasoning on k.
Basis (k = 1).
— Implication 1. Assume P `1S,D,C ϕ. Then, due to the single SQDA inference,
α
there must exist some Rl = (q(sn ) ←
−) ∈ P with empty body, some substitution
θ and some d0 , d1 , . . . , dn ∈ D \ {b} such that P `0S,D,C (ti == si θ)]di ⇐ Π for
i = 1 . . . n, S(p, q) = d0 6= b, d P di (0 ≤ i ≤ n) and d P α. Then ⊥⊥ `0S,D,C (ti ==
si θ)]di ⇐ Π holds for i = 1 . . . n, because of Lemma 3.1(1). Therefore ϕ is an
immediate consequence of ⊥
⊥ via Rl , which guarantees ϕ ∈ TP ↑1 (⊥⊥).
— Implication 2. Assume now ϕ ∈ TP ↑1 (⊥⊥). Then ϕ must be an immediate
α
consequence of ⊥
⊥ via some Rl = (q(sn ) ←
−) ∈ P with empty body. Then there are
some substitution θ and some d0 , d1 , . . . , dn ∈ D \{b} such that ⊥⊥ ``S,D,C (ti ==
si θ)]di ⇐ Π for i = 1 . . . n, S(p, q) = d0 6= b, d P di (0 ≤ i ≤ n) and d P α.
Again because of Lemma 3.1(1), we get P `0S,D,C (ti == si θ)]di ⇐ Π for i =
1 . . . n, which guarantees P `1S,D,C ϕ with one single SQDA inference using Rl
instantiated by θ.

Fixpoint & Proof-theoretic Semantics for SQCLP

39

Inductive step (k > 1).
— Implication 1. Assume P `kS,D,C ϕ. Since the root inference must be SQDA,
α
there must exist some program rule (Rl : q(sn ) ←
− B1 ]w1 , . . . , Bm ]wm ) ∈ P, some
substitution θ and some qualification values d0 , d1 , . . . , dn , e1 , . . . , em ∈ D \ {b}
such that
• P `0S,D,C φi = ((ti == si θ)]di ⇐ Π) for i = 1 . . . n,
k

j
• P `S,D,C
ψj = (Bj θ]ej ⇐ Π) with ej Q? wj for j = 1 . . . m, and
• S(p, q) = d0 6= b, d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤ j ≤ m)

where Σm
j=1 kj = k − 1. For each j = 1 . . . m, either ψj is defined, and then in0

duction hypothesis yields some kj0 such that ψj ∈ TP ↑kj (⊥⊥) and therefore also
0

0

TP ↑kj (⊥
⊥) ``S,D,C ψj ; or else ψj is not defined and then TP ↑kj (⊥⊥) ``S,D,C ψj for
any arbitrarily chosen kj0 , by Lemma 3.1(1). Then l = max{kj0 | 1 ≤ j ≤ m}
verifies that ϕ is an immediate consequence of TP ↑l (⊥⊥) via Rl , which implies
0
ϕ ∈ TP ↑k (⊥
⊥) for k 0 = l + 1.
— Implication 2. Assume ϕ ∈ TP ↑k (⊥⊥) = TP (TP ↑k−1 (⊥⊥)). Then ϕ is an imα
− B1 ]w1 , . . . ,
mediate consequence of T p↑k−1 (⊥⊥) via some clause (Rl : q(sn ) ←
Bm ]wm ) ∈ P. Therefore, there exist some substitution θ and some qualification
values d0 , d1 , . . . , dn , e1 , . . . , em ∈ D \ {b} such that:
• TP ↑k−1 (⊥
⊥) ``S,D,C φi = ((ti == si θ)]di ⇐ Π) for i = 1 . . . n,
• TP ↑k−1 (⊥
⊥) ``S,D,C ψj = (Bj θ]ej ⇐ Π) with ej Q? wj for j = 1 . . . m, and
• S(p, q) = d0 6= b, d P di (0 ≤ i ≤ n) and d P α ◦ ej (1 ≤ j ≤ m).
For each i = 1 . . . n, Lemma 3.1(1) yields P `0S,D,C φi . For each j = 1 . . . m,
either ψj is defined, in which case ψj ∈ TP ↑k−1 (⊥⊥), k − 1 ≥ 1, and induction
k0

j
hypothesis yields some kj0 such that P `S,D,C
ψj ; or else ψj is not defined, in which

k0

0

j
case P `S,D,C
ψj for kj0 = 0, by Lemma 3.1(1). In these conditions, P `kS,D,C ϕ
0
holds for k 0 = 1 + Σm
j=1 kj , with a proof tree using a SQDA root inference based
on Rl instantiated by θ.

As an easy consequence of the previous theorem we get:
Corollary 3.1 (SQCHL(S, D, C) is sound and complete)
For any SQCLP(S, D, C)-program P and any observable qc-atom ϕ, the following
three statements are equivalent:
(a) P `S,D,C ϕ

(b) P |=S,D,C ϕ

Moreover, we also have:
1. Soundness: P `S,D,C ϕ =⇒ P |=S,D,C ϕ.
2. Completeness: P |=S,D,C ϕ =⇒ P `S,D,C ϕ.

(c) MP ``S,D,C ϕ

40

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

Proof
Soundness and completeness are just a trivial consequence of (a) ⇔ (b). To finish
the proof it suffices to prove the two equivalences (a) ⇔ (c) and (b) ⇔ (c). This is
done as follows:
[(a) ⇔ (c)] In the case that ϕ is a defined qc-atom, MP ``S,D,C ϕ reduces to ϕ ∈ MP
which is equivalent to P `S,D,C ϕ by Theorem 3.2. Otherwise, P `S,D,C ϕ ⇐⇒
MP ``S,D,C ϕ holds because of Lemma 3.1(1).
[(b) ⇒ (c)] Assume P |=S,D,C ϕ and recall Definition 3.3. Then I ``S,D,C ϕ for
every qc-interpretation I such that I |=S,D,C P. In particular, MP ``S,D,C ϕ, since
MP |=S,D,C P was proved in Theorem 3.1.
[(c) ⇒ (b)] Assume MP ``S,D,C ϕ. In order to obtain P |=S,D,C ϕ we must prove:
(?) I ``S,D,C ϕ holds for any qc-interpretation I such that I |=S,D,C P .
In the case that ϕ is a defined qc-atom, MP ``S,D,C ϕ reduces to ϕ ∈ MP , which
implies (?) because MP is the least model of P, as proved in Theorem 3.1. In the
case that ϕ is not defined but C-based, (?) follows form the fact that I ``S,D,C ϕ
holds for any arbitrary qc-interpretation I, as proved in Lemma 3.1(1).
We close this subsection with a brief discussion on the relationship between the
entailment relation <D,C used in this report and a different one that was proposed
in (Caballero et al. 2008) and noted <S,D. In contrast to <D,C , the entailment <S,D
depended on a given similarity relation S. In the context of the SQCLP scheme, one
could think of an entailment <S,D,C depending on S and defined in the following
way: given two qc-atoms ϕ and ϕ0 , we could say that ϕ (S, D, C)-entails ϕ0 (in
symbols, ϕ <S,D,C ϕ0 ) iff ϕ : A]d ⇐ Π and ϕ0 : A0 ]d0 ⇐ Π0 such that there is some
substitution θ satisfying S(A0 , Aθ) = λ 6= b, d0 P λ, d0 P d and Π0 |=C Πθ.
However, <S,D,C would not work properly in the case that S is not transitive,
as shown by the following simple example: think of a SQCLP(S, U, R)-program P
including just a clause
1.0

R1 : p1 ←−−
and assume that S verifies S(p1 , p2 ) = 0.9, S(p2 , p3 ) = 0.9 and S(p1 , p3 ) = 0.4 where
p1 , p2 , p3 ∈ DP 0 . Then, P `S,U ,R p2 ]0.9 ⇐ ∅ can be easily proved with the SQCHL
rule SQDA and p2 ]0.9 ⇐ ∅ <S,U ,R p3 ]0.9 ⇐ ∅ holds because of S(p2 , p3 ) = 0.9,
but P `S,U ,R p3 ]0.9 ⇐ ∅ does not hold. Therefore, the Entailment Property for
Programs (Lemma 3.1(2)) would fail if the entailment <S,D,C were adopted in place
of <D,C .
Since the Entailment Property for Programs is a very natural condition that must
be preserved, we conclude that the entailment relation <D,C used in this report is
the right choice in a framework where the underlaying proximity relation is not
guaranteed to be a similarity.
3.2 Goals and their Solutions
In this brief subsection we present the syntax and declarative semantics of goals in
the SQCLP scheme, and we define natural soundness and completeness properties

Fixpoint & Proof-theoretic Semantics for SQCLP

41

which are expected to be fulfilled by goal solving devices. These notions are intended
as a useful tool to reason about the correctness of SQCLP implementations to be
developed in the future.
In order to build goals for SQCLP(S, D, C)-programs, we assume a countably
infinite set War of so-called qualification variables W , disjoint from Var and C’s
signature Σ. Goals for a given program P have the form
G : A1 ]W1 , . . . , Am ]Wm 8 W1 Q? β1 , . . . , Wm Q? βm

abbreviated as (Ai ]Wi , Wi Q? βi )i=1...m , where Ai ]Wi (1 ≤ i ≤ m) are atoms
annotated with different qualification variables Wi ; and Wi Q? βi are so-called
threshold conditions with βi ∈ (D \ {b}) ] {?} (1 ≤ i ≤ m). The notations ? and
Q? have been already explained in Section 3.1.
In the sequel, the notation war(o) will denote the set of all qualification variables
occurring in the syntactic object o. In particular, for a goal G as displayed above,
war(G) denotes the set {Wi | 1 ≤ i ≤ m}. In the case m = 1 the goal is called
atomic. The declarative semantics of goals is provided by their solutions, that are
defined as follows:
Definition 3.5 (Goal Solutions)
Assume a given SQCLP(S, D, C)-program P and a goal G for the program P with
the syntax displayed above. Then:
1. A solution for G is any triple hσ, µ, Πi such that σ is a C-substitution, µ :
war(G) → D \ {b}, Π is a satisfiable and finite set of atomic C-constraints
and the following two conditions hold for all i = 1 . . . m:
(a) Wi µ = di Q? βi and
(b) P `S,D,C Ai σ]Wi µ ⇐ Π.
The set of all solutions for G is noted SolP (G). Note that solutions are open
in the sense that the substitution σ is not required to be ground.
2. A solution hη, ρ, Πi for G is called ground iff Π = ∅ and η ∈ ValC is a variable
valuation such that Ai η is a ground atom for all i = 1 . . . m. The set of all
ground solutions for G is noted GSolP (G). Obviously, GSolP (G) ⊆ SolP (G).
3. A ground solution hη, ρ, ∅i ∈ GSolP (G) is subsumed by hσ, µ, Πi iff there is
some ν ∈ SolC (Π) s.t. η =var(G) σν and Wi ρ P Wi µ for i = 1 . . . m.
Implicitly, the first item in the previous definition requires Ai σ]Wi µ ⇐ Π to be
observable qc-atoms in the sense of Definition 3.1, which is trivially true because
Wi µ = di ∈ D \ {b} and Π is satisfiable. In fact, Definition 3.1 was designed with
the aim of using observable qc-atoms as observations of valid open solutions for
atomic goals. The next example illustrates the definition:
Example 3.6 (Solutions for an atomic goals)
1. G : goodWork(X)]W 8 W Q (0.55,30) is a goal for the program fragment P
shown in Figure 1, and the arguments given near the beginning of Subsection
3.1 can be formalized to prove that h{X 7→ king liar}, {W 7→ (0.6,5)}, ∅i ∈
SolP (G).

42

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az
2. As an additional example involving constraints, recall the SQCLP(S, U, R)program P presented in Example 3.1. An atomic goal G for this program is
p0 (c0 (Y ), Z)]W 8 W ≥? 0.75. Consider σ = {Z 7→ c(X)}, µ = {W 7→ 0.8} and
Π = {cp> (X, 1.0), op+ (A, A, X), op× (2.0, A, Y )}. Note that 0.8 ≥ 0.75 and
P `S,U ,R p0 (c0 (Y ), Z)σ]W µ ⇐ Π, as we have seen in Example 3.5. Therefore,
the requirements of Definition 3.5 are fulfilled, and hσ, µ, Πi ∈ SolP (G).

In practice, users of SQCLP languages will rely on some available goal solving system for computing goal solutions. The following definition specifies two important
properties of goal solving systems:
Definition 3.6 (Correct Goal Solving Systems)
At a high abstraction level, a goal solving system for SQCLP(S, D, C) can be thought
as a device that takes a program P and a goal G as input and yields various triples
hσ, µ, Πi, called computed answers, as outputs. Such a goal solving system is called:
1. Sound iff every computed answer is a solution hσ, µ, Πi ∈ SolP (G).
2. Weakly complete iff every ground solution hη, ρ, ∅i ∈ GSolP (G) is subssumed
by some computed answer.
3. Correct iff it is both sound and weakly complete.
Every goal solving system for a SQCLP instance should be sound and ideally
also weakly complete. Implementing such systems is one of the major lines of future
research mentioned in the Conclusions of this report.
4 Conclusions
We have extended the classical CLP scheme to a new scheme SQCLP whose instances SQCLP(S, D, C) are parameterized by a proximity relation S, a qualification
domain D and a constraint domain C. In addition to the known features of CLP
programming, the new scheme offers extra facilities for dealing with expert knowledge representation and flexible query answering. Inspired by the observable CLP
semantics in (Gabbrielli and Levi 1991; Gabbrielli et al. 1995), we have presented a
declarative semantics for SQCLP that provides fixpoint and proof-theoretical characterizations of least program models as well as an implementation-independent
notion of goal solutions.
SQCLP is a quite general scheme. Different partial instantiations of its three
parameters lead to more particular schemes, most of which can be placed in close
correspondence to previous proposals. The items below present seven particularizations, along with some comments which make use of the notions threshold-free,
attenuation-free and constraint-free which have been explained at the beginning of
Section 3.1.
1. By definition, QCLP has instances QCLP(D, C) =def SQCLP(Sid , D, C), where
Sid is the identity proximity relation. The quantitative CLP scheme proposed
in (Riezler 1998) can be understood as a further particularization of QCLP
that works with threshold-free QCLP(U, C) programs, where U is the qualification domain of uncertainty values (see Subsection 2.2.2).

Fixpoint & Proof-theoretic Semantics for SQCLP

43

2. By definition, SQLP has instances SQLP(S, D) =def SQCLP(S, D, R), where
R is the real constraint domain (see Subsection 2.1.2). The scheme with the
same name originally proposed in (Caballero et al. 2008) can be understood
as a restricted form of the present formulation; it worked with threshold-free
and constraint-free SQLP(S, D) programs and it restricted the choice of the
S parameter to transitive proximity (i.e. similarity) relations.
3. By definition, SCLP3 has instances SCLP(S, C) =def SQCLP(S, B, C), where
B is the qualification domain of classical boolean values (see Subsection 2.2.1).
Due to the fixed parameter choice D = B, both attenuation values and threshold values become useless, and each choice of S must necessarily represent a
crisp reflexive and symmetric relation. Therefore, this new scheme is not so
interesting from the viewpoint of uncertain and qualified reasoning.
4. By definition, QLP has instances QLP(D) =def SQCLP(Sid , D, R). The scheme
with the same name originally proposed in (Rodrı́guez-Artalejo and RomeroDı́az 2008b) can be understood as a restricted form of the present formulation;
it worked with threshold-free and constraint-free QLP(D) programs.
5. By definition, SLP has instances SLP(S) =def SQCLP(S, U, R). The pure
fragment of Bousi~Prolog (Julián-Iranzo and Rubio-Manzano 2009a) can be
understood as a restricted form of SLP in the present formulation; it works
with threshold-free, attenuation-free and constraint-free SLP(S) programs.
Moreover, restricting the choice of S to similarity relations leads to SLP in
the sense of (Sessa 2002) and related papers.
6. The CLP scheme can be defined by instances CLP(C) =def SQCLP(Sid , B, C).
Both attenuation values and threshold values are useless in CLP programs,
due to the fixed parameter choice D = B.
7. Finally, the pure LP paradigm can be defined as LP =def SQCLP(Sid , B, H),
where H is the Herbrand constraint domain. Again, attenuation values and
threshold values are useless in LP due to the fixed parameter choice D = B.
In all the previous items, the schemes obtained by partial instantiation inherit the
declarative semantics from SQCLP, using sets of observables of the form A]d ⇐ Π
as interpretations. A similar semantic approach were used in our previous papers
(Rodrı́guez-Artalejo and Romero-Dı́az 2008b; Caballero et al. 2008), except that Π
and equations were absent due to the lack of CLP features. The other related works
discussed in the Introduction view program interpretations as mappings I from the
ground Herbrand base into some set of lattice elements (the real interval [0, 1] in
many cases), as already discussed in the explanations following Definition 3.2.
As seen in Subsection 3.2, SQCLP’s semantics enables a declarative characterization of valid goal solutions. This fact is relevant for modeling the expected behavior
of goal solving devices and reasoning about their correctness. Moreover, the relations ≈λ,Π introduced for the first time in the present paper (see Definition 2.16)
allow to specify the semantic role of S in a constraint-based framework, with less
technical overhead than in previous related approaches.
3

Not to be confused with SCLP in the sense of (Bistarelli et al. 2001), discussed below.

44

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

A related work not mentioned in items 1–7 above is the semiring-based CLP
of (Bistarelli et al. 2001), a scheme with instances SCLP(S) parameterized by a
semiring S = hA, +, ×, 0, 1i whose elements are used to represent consistency levels
in soft constraint solving. The semirings used in this approach can be equipped
with a lattice structure whose lub operation is always +, but whose glb operation
may be different from ×. On the other hand, our qualification domains are defined
as lattices with an additional attenuation operation ◦. It turns out that the kind
of semirings used in SCLP(S) correspond to qualification domains only in some
cases. Moreover, × is used in SCLP(S) to interpret logical conjunction in clause
bodies and goals, while the glb operation is used in SQCLP(S, D, C) for the same
purpose. For this reason, even if D is “equivalent” to S, SQCLP(S, D, C) cannot
be naturally used to express SCLP(S) in the case that × is not the glb. Assuming
that D is “equivalent” to S and that × behaves as the glb in S, program clauses in
SCLP(S) can be viewed as a particular case of program clauses in SQCLP(S, D, C)
which use an attenuation factor different from t only for facts. Other relevant
differences between SQCLP(S, D, C) and SCLP(S) can be explained by comparing
the parameters. As said before D may be “equivalent” to S in some cases, but
S is absent and C is not made explicit in SCLP(S). Seemingly, the intended use
of SCLP(S) is related to finite domain constraints and no parametrically given
constraint domain is provided.
In the future we plan to implement some SQCLP instances by extending the semantically correct program transformation techniques from (Caballero et al. 2008),
and to investigate applications which can profit from flexible query answering. Other
interesting lines of future work include: a) extension of the qualified SLD resolution presented in (Rodrı́guez-Artalejo and Romero-Dı́az 2008b) to a SQCLP goal
solving procedure able to work with constraints and a proximity relation; and b)
extension of the QCFLP scheme in (Caballero et al. 2009) to work with a proximity
relation and higher-order functions.
Acknowledgements
This report is a widely extended version of (Rodrı́guez-Artalejo and Romero-Dı́az
2010). The authors are thankful to the anonymous referees of (Rodrı́guez-Artalejo
and Romero-Dı́az 2010) for constructive remarks and suggestions which helped to
improve the presentation. They are also thankful to Rafael Caballero for useful discussions on the report’s topics and to Jesús Almendros for pointing to bibliographic
references in the area of flexible query answering.
References
Apt, K. R. 1990. Logic programming. In Handbook of Theoretical Computer Science,
J. van Leeuwen, Ed. Vol. B: Formal Models and Semantics. Elsevier and The MIT Press,
493–574.
Apt, K. R. and Gabbrielli, M. 1994. Declarative interpretations reconsidered. In
Proceedings of the 11th International Conference on Logic Programming (ICLP’94),
P. van Hentenryck, Ed. The MIT Press, 74–89.

Fixpoint & Proof-theoretic Semantics for SQCLP

45

Apt, K. R. and van Emden, M. H. 1982. Contributions to the theory of logic programming. Journal of the Association for Computing Machinery (JACM) 29, 3, 841–862.
Arcelli, F. and Formato, F. 1999. Likelog: a logic programming language for flexible data retrieval. In Proceedings of the 1999 ACM Symposium on Applied computing
(SAC’99). ACM Press, New York, NY, USA, 260–267.
Arenas, P., Fernández, A. J., Gil, A., López-Fraguas, F. J., Rodrı́guez-Artalejo,
M., and Sáenz-Pérez, F. 2007. T OY, a multiparadigm declarative language (version
2.3.1). In R. Caballero and J. Sánchez, editors, User Manual, available at http://toy.
sourceforge.net.
Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University
Press.
Bistarelli, S., Montanari, U., and Rossi, F. 2001. Semiring-based constraint logic
programming: Syntax and semantics. ACM Transactions on Programming Languages
and Systems 3, 1 (January), 1–29.
Bossi, A., Gabbrielli, M., Levi, G., and Martelli, M. 1994. The s-semantics approach: Theory and applications. Journal of Logic Programming 19/20, 149–197.
Caballero, R., Rodrı́guez-Artalejo, M., and Romero-Dı́az, C. A. 2008. Similaritybased reasoning in qualified logic programming. In PPDP ’08: Proceedings of the 10th
international ACM SIGPLAN conference on Principles and Practice of Declarative Programming. ACM, Valencia, Spain, 185–194.
Caballero, R., Rodrı́guez-Artalejo, M., and Romero-Dı́az, C. A. 2009. Qualified
computations in functional logic programming. In Logic Programming (ICLP’09), P. Hill
and D. Warren, Eds. LNCS, vol. 5649. Springer-Verlag Berlin Heidelberg, Pasadena, CA,
USA, 449–463.
Clark, K. L. 1979. Predicate logic as a computational formalism (res. report doc 79/59).
Tech. rep., Imperial College, Dept. of Computing, London.
Dubois, D. and Prade, H. 1980. Fuzzy Sets and Systems: Theory and Applications.
Academic Press, New York, NY, USA.
Estévez-Martı́n, S., Hortalá-González, T., Rodrı́guez-Artalejo, M., del
Vado Vı́rseda, R., Sáenz-Pérez, F., and Fernández, A. J. 2009. On the cooperation of the constraint domains H, R and FD in cf lp. Theory and Practice of Logic
Programming 9, 4, 415–527.
Falaschi, M., Levi, G., Martelli, M., and Palamidessi, C. 1993. A model-theoretic
reconstruction of the operational semantics of logic programs. Information and Computation 102, 1, 86–113.
Falaschi, M., Levi, G., Palamidessi, C., and Martelli, M. 1989. Declarative modeling
of the operational behavior of logic languages. Theoretical Computer Science 69, 3
(December), 289–318.
Freuder, E. C. and Wallace, R. J. 1992. Partial constraint satisfaction. Artificial
Intelligence 58, 1–3, 21–70.
Gabbrielli, M., Dore, G. M., and Levi, G. 1995. Observable semantics for constraint
logic programs. Journal of Logic and Computation 5, 2, 133–171.
Gabbrielli, M. and Levi, G. 1991. Modeling answer constraints in constraint logic
programs. In Proceedings of the 8th International Conference on Logic Programming
(ICLP’91). The MIT Press, 238–252.
Georget, Y. and Codognet, P. 1998. Compiling semiring-based constraints with
CLP(FD,S). In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. LNCS, vol. 1520. Springer-Verlag, 205–219.
Guadarrama, S., Muñoz, S., and Vaucheret, C. 2004. Fuzzy prolog: A new approach
using soft constraint propagation. Fuzzy Sets and Systems 144, 1, 127–150.

46

M. Rodrı́guez-Artalejo and C. A. Romero-Dı́az

Hájek, P. 1998. Metamathematics of Fuzzy Logic. Dordrecht: Kluwer.
Hanus, Ed., M. Curry: An integrated functional logic language (vers. 0.8.2, 2006); http:
//www.curry-language.org.
Höhfeld, M. and Smolka, G. 1988. Definite relations over constraint languages. Tech.
Rep. LILOG Report 53, IBM Deutschland.
Jaffar, J. and Lassez, J. L. 1987. Constraint logic programming. In Proceedings of the
14th ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages
(POPL’87). ACM New York, NY, USA, Munich, West Germany, 111–119.
Jaffar, J. and Maher, M. 1994. Constraint logic programming: a survey. Journal of
Logic Programming 19&20, 503–581.
Jaffar, J., Maher, M., Marriott, K., and Stuckey, P. J. 1998. Semantics of constraints logic programs. Journal of Logic Programming 37, 1-3, 1–46.
Jaffar, J., Michaylov, S., Stuckey, P. J., and Yap, R. H. C. 1992. The CLP(R) language and system. ACM Transactions on Programming Languages and Systems 14(3),
339–395.
Julián-Iranzo, P., Rubio, C., and Gallardo, J. 2009. Bousi∼Prolog: a prolog extension language for flexible query answering. In Proceedings of the Eighth Spanish Conference on Programming and Computer Languages (PROLE 2008), J. M. AlmendrosJiménez, Ed. ENTCS, vol. 248. Elsevier, Gijón, Spain, 131–147.
Julián-Iranzo, P. and Rubio-Manzano, C. 2009a. A declarative semantics for
Bousi∼Prolog. In PPDP’09: Proceedings of the 11th ACM SIGPLAN conference on
Principles and practice of declarative programming. ACM, Coimbra, Portugal, 149–160.
Julián-Iranzo, P. and Rubio-Manzano, C. 2009b. A similarity-based WAM for
Bousi∼Prolog. In Bio-Inspired Systems: Computational and Ambient Intelligence
(IWANN 2009). LNCS, vol. 5517. Springer Berlin / Heidelberg, Salamanca, Spain, 245–
252.
Kifer, M. and Subrahmanian, V. S. 1992. Theory of generalized annotated logic
programs and their applications. Journal of Logic Programming 12, 3&4, 335–367.
Krajči, S., Lencses, R., and Vojtáš, P. 2004. A comparison of fuzzy and annotated
logic programming. Fuzzy Sets and Systems 144, 173–192.
Lloyd, J. W. 1987. Foundations of Logic Programming, Second Edition. Springer.
Loia, V., Senatore, S., and Sessa, M. I. 2004. Similarity-based SLD resolution and
its role for web knowledge discovery. Fuzzy Sets and Systems 144, 1, 151–171.
López-Fraguas, F. J., Rodrı́guez-Artalejo, M., and del Vado-Vı́rseda, R. 2007.
A new generic scheme for functional logic programming with constraints. Journal of
Higher-Order and Symbolic Computation 20, 1&2, 73–122.
Lucio, P., Orejas, F., Pasarella, E., and Pino, E. 2008. A functorial framework for
constraint normal logic programming. Applied Categoriacal Structures 16, 3, 421–450.
Medina, J., Ojeda-Aciego, M., and Vojtáš, P. 2001a. Multi-adjoint logic programming with continuous semantics. In Logic Programming and Non-Monotonic Reasoning
(LPNMR’01), T. Eiter, W. Faber, and M. Truszczyinski, Eds. LNAI, vol. 2173. SpringerVerlag, 351–364.
Medina, J., Ojeda-Aciego, M., and Vojtáš, P. 2001b. A procedural semantics for
multi-adjoint logic programming. In Progress in Artificial Intelligence (EPIA’01),
P. Brazdil and A. Jorge, Eds. LNAI, vol. 2258. Springer-Verlag, 290–297.
Moreno, G. and Pascual, V. 2007. Formal properties of needed narrowing with similarity relations. Electronic Notes in Theoretical Computer Science 188, 21–35.
Ng, R. T. and Subrahmanian, V. S. 1992. Probabilistic logic programming. Information
and Computation 101, 2, 150–201.

Fixpoint & Proof-theoretic Semantics for SQCLP

47

Riezler, S. 1996. Quantitative constraint logic programming for weighted grammar applications. In Proceedings of the Logical Aspects of Computational Linguistics (LACL’96),
C. Retoré, Ed. LNCS, vol. 1328. Springer-Verlag, 346–365.
Riezler, S. 1998. Probabilistic constraint logic programming. Ph.D. thesis, Neuphilologischen Fakultät del Universität Tübingen.
Rodrı́guez-Artalejo, M. and Romero-Dı́az, C. A. 2008a. A generic scheme for qualified logic programming. Tech. Rep. SIC-1-08 (CoRR abs/1008.3863), Universidad Complutense, Departamento de Sistemas Informáticos y Computación, Madrid, Spain.
Rodrı́guez-Artalejo, M. and Romero-Dı́az, C. A. 2008b. Quantitative logic programming revisited. In Functional and Logic Programming (FLOPS’08), J. Garrigue
and M. Hermenegildo, Eds. LNCS, vol. 4989. Springer-Verlag, Ise, Japan, 272–288.
Rodrı́guez-Artalejo, M. and Romero-Dı́az, C. A. 2009. Qualified logic programming
with bivalued predicates. In Proceedings of the Eighth Spanish Conference on Programming and Computer Languages (PROLE 2008), J. M. Almendros-Jiménez, Ed. ENTCS,
vol. 248. Elsevier, Gijón, Spain, 67–82.
Rodrı́guez-Artalejo, M. and Romero-Dı́az, C. A. 2010. A declarative semantics for
CLP with qualification and proximity. Theory and Practice of Logic Programming, 26th
Int’l. Conference on Logic Programming (ICLP’10) Special Issue 10, 4–6, 627–642.
Saraswat, V. A. 1992. The category of constraint systems is cartesian-closed. In Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS
’92). 341–345.
Sessa, M. I. 2002. Approximate reasoning by similarity-based SLD resolution. Theoretical
Computer Science 275, 1-2, 389–426.
Shenoi, S. and Melton, A. 1999. Proximity relations in the fuzzy relational database
model. Fuzzy Sets and Systems 100, supl., 51–62.
Tarski, A. 1955. A lattice-theoretical fixpoint theorem and its applications. Pacific
Journal of Mathematics 5, 2, 285–309.
van Emden, M. H. 1986. Quantitative deduction and its fixpoint theory. Journal of Logic
Programming 3, 1, 37–53.
van Emden, M. H. and Kowalski, R. A. 1976. The semantics of predicate logic
as a programming language. Journal of the Association for Computing Machinery
(JACM) 23, 4, 733–742.
Vaucheret, C., Guadarrama, S., and Muñoz, S. 2002. Fuzzy prolog: A simple general
implementation using CLP(R). In Logic for Programming, Artificial Intelligence, and
Reasoning (LPAR’02), M. Baaz and A. Voronkov, Eds. LNCS, vol. 2514. Springer Berlin
/ Heidelberg, Tbilisi, Georgia, 450–463.
Vojtáš, P. 2001. Fuzzy logic programming. Fuzzy Sets and Systems 124, 361–370.
Zadeh, L. A. 1965. Fuzzy sets. Information and Control 8, 3, 338–353.
Zadeh, L. A. 1971. Similarity relations and fuzzy orderings. Information Sciences 3, 2,
177–200.

