Semiring-based Constraint Logic Programming

1 Introduction

Classical constraint satisfaction problems (CSPs) [Mac92] are a very expressive and natural formalism to specify many kinds of real-life problems. However, they also have evident limitations, mainly when they are used to represent real-life scenarios where the knowledge is not completely available nor crisp. In fact, in such sit­ uations, the ability of stating whether an instantiation of values to variables is allowed or not is not enough or sometimes not even possible. Recently, a proposal which extends classical CSPs in this direction has been developed [BMR95; BMR97], which is able to model many desired features, like fuzzyness [DFP93], proba­ bility [FL93], uncertainty, partiality [FW92], hierarchy [BMMW89], and optimization. This framework is based on the observation that a semiring (that is, a domain plus two operations satisfying certain properties) is all what is needed to describe many constraint satisfaction schemes. In fact, the domain of the semiring provides the levels of consistency (which can be interpreted as cost, or degrees of preference, or probabilities, or oth­ ers) , and the two operations define how to combine con­ straints together. In particular, from one of the opera­ tions we can derive a partial order ::::; among the elements of the semiring which allows us to compare different el­ ements: if a ::::; b then it means that b is better than a. This is crucial in situations which involve some kind of optimization. Constraint problems described according to this framework are called SCSP (for Semiring-based Constraint Satisfaction Problems).

·On leave at SRI International, Menlo Park, CA.

Constraint logic programming (CLP) [JL87]languages extended logic programming (LP) by replacing term equalities with constraints and unification with con­ straint solving. Programming in CLP means choosing a constraint system for a specific class of constraints (for example, linear arithmetic constraints, or finite domain constraints) and embedding it into a logic programming engine. This approach is very flexible since one can choose among many constraint systems without chang­ ing the overall programming language, and has shown to be very successful in specifying and solving complex problems in terms of constraints of various kind. How­ ever, it can handle only classical constraint solving. Thus it is natural to try to extend the CLP formalism in order to be able to handle also SCSP problems. We will call such an extension SCLP (for Semiring-based CLP) .

In passing from CLP to SCLP languages, we will re­ place classical constraints with the more general SCSP constraints. By doing this, we also have to modify the notions of interpretation, model, model intersection, and others, since we have to take into account the semiring operations and not the usual CLP operations. For ex­ ample, while CLP interpretations associate a truth value (either true or false) to each ground atom, here ground atoms must be given one of the elements of the semir­ ing. Also, while in CLP the value associated to an ex­ istentially quantified atom is the logical or among the truth values associated to each of its instantiations, here we have to replace the or with another operation which refers to one of the semiring operations.

After describing the syntax of SCLP programs, we will define three equivalent semantics for such languages: model- theoretic, fixpoint , and operational. These se­ mantics are conservative extensions of the corresponding ones for LP, since by choosing a particular semir­ ing (the one with just two elements, true and false, and the logical and and or as the two semiring operations) we get exactly the LP semantics. The extension is in some cases predictable but it possesses some crucial new features. For example, the presence of a partial order among the semiring elements (and not a total order like it is in the LP /CLP case, where we just have two com­ parable elements) brings some conceptual complexity in some aspects of the semantics. In fact, in the operational semantics there could be two refutations for a goal which lead to different semiring elements which are not com­ parable in the partial order. In this case, these elements have to be combined in order to get the solution corre­ sponding to the given goal, and their combination could be not reachable by any derivation path in the search tree. This means that any constructive way to get such a solution by visiting the search tree would have to fol­ low all the incomparable paths before being able to find the correct answer.

A related approach is HCLP (Hierarchical CLP) [BMMW89], where each constraint has a level of impor­ tance (like strong, weak, required), and these levels are used to decide which constraints to satisfy. However, a constraint can only be satisfied or not, and thus HCLP is a crisp formalism. Moreover, their treatment is only algorithmic, and they do not provide their language with a fixpoint or a model-theoretic semantics.

A recent approach to multi-valued logic programming [MPS97] uses bilattices with two orderings to model both truth and knowledge levels. The resulting logic program­ ming semantics is just operational and fixpoint, while no model-theoretic semantics is presented. Moreover, the presence in our approach of just one ordering (modelling truth levels) is not a restriction, since the vectoriza­ tion of several semirings is still a semiring (see [BMR95; BMR97)) and thus optimization based on multiple crite­ ria can be cast in our framework as well.

2 Semiring-based CSPs

Here we give the basic notions about constraint solving over semirings, introduced in [BMR95; BMR97].

Definition 1 (semiring) A semiring is a tuple (A, + , x, 0, 1) such that

• A is a set and 0, 1 E A;
• +, called the additive operation, is a closed (i.e., a, bE A implies a+ bE A), commutative (i .e., a+ b = b +a) and associative (i.e., a+ (b +c) = (a+
• b)+ c) operation such that a+ 0 =a= 0 +a (i.e.,
• 0 is its unit element);
• x, called the multiplicative operation, is a closed and associative operation such that 1 is its unit element

and a x 0 = 0 = 0 x a (i.e., 0 is its absorbing element);

• x distributes over+ (i.e., ax (b +c) = (a x b)+ (a x c)). 0

Definition 2 ( c-semiring) A c-semiring is a semi ring (A,+, x, 0, 1) such that

• + is idempotent (i.e ., a E A implies a+ a= a);
• x is commutative;
• 1 is the absorbing element of +.

0

The following is a list of properties about c-semirings which will be used in this paper:

• Given any c-semiring S = (A,+, x, 0, 1), the rela­ tion 5os over A such that a 5os b iff a+ b = b is a partial order.
• Since 0 is the unit element of the additive operation, it is the minimum element of the ordering. Thus, for any a E A, we have 0 5os a.
• Both the additive and the multiplicative operation are monotone on the ordering S,s.
• Since 1 is also the absorbing element of the addi­ tive operation, then a 5os 1 for all a. Thus 1 is the maximum element of the partial ordering. This im­ plies that the x operation is intensive, that is, that a x b 5os a. This is important since it means that combining more constraints leads to a worse (w.r.t. the 5os ordering) result.
• Given a c-semiring S =(A,+, x, 0,1), and its par­ tial order S,s, (A, 5os) is a complete lattice 1 . More­ over, for any a, bE A, we have a V b =a+ b, where V is the lub operation of the lattice.
• Given a c-semiring S = (A,+, x, 0, 1), consider the corresponding lattice (A, 5os). If x is idempotent, then we have that:
• + distributes over x;
• x = 1\, where 1\ is the glb operation of the lattice;
• (A, 5os) is a distributive lattice.

Definition 3 (SCSP s) A constraint problem based on semirings (SCSP) consists of a set of variables with a fi­ nite domain D and a set of constraints. Each constraint, which connects a subset of the variables V, is defined by associating an element of the semiring with each tuple of values of D for the variables in V. 0

Note that the elements of the chosen semiring can be interpreted in many ways: cost, level of preference, certainty, probability, etc. Note also that the intuitive meaning of the partial order 5os is to state when an ele­ ment is better than another one: if a 5os b then we mean that b is better than a. Finally, it is interesting to notice that classical CSPs are just SCSPs where the semiring has just two values: true and false , and the two opera­ tions are logical and and logical or. That is, the semiring is Scsp = ({true,false},V,I\,false , true).

1 Actually, for this result to hold we must assume that there exists the sum of an infinite number of elements.

3 Syntax of SCLP programs

SCLP(S,D) programs are just Constraint Logic Pro­ gramming (CLP) programs [JL87] where constraints are handled according to the chosen semiring S = (A,+, x, 0, 1) and variables can be assigned values over a. finite set D. As usual, a program is a set of clauses. Each clause is then composed by a head and a body. The head is just an atom and the body is either a collection of atoms, or a value of the semiring. Finally, a goal is a collection of atoms. The BNF for this syntax follows.

H ::AT where AT is the category of atoms

p :: CL I CL,P CL :: H: -B LAT :: o I LAT, AT B :: LAT I a where a E A

G :: : -LAT

As an example, consider the following SCLP(S,D) pro­ gram where S = ( -N U { -oo }, max,+, -oo, 0) , -N is the set of non-positive integers, and D = {a, b, c}. Note that the ordering 5os in this semiring coincides with the 5: ordering over integers.

s(x) p(x,y).

p(a,b) q(a).

p(a,c) r(a).

q(a) t(a).

t (a) -2.

r(a) -3.

The intuitive meaning of a semiring value like -3 as­ sociated to the atom r(a) is that r(a) costs 3 units. Thus the set - N U { -oo} contains all possible costs, and the choice of the two operations max and + implies that we intend to maximize the sum of the costs. This gives us the possibility to select the atom instantiation which gives the minimal cost overall.

4 Model-theoretic semantics

An interpretation is a function which takes a predi­ cate and an instantiation of its arguments (that is, a ground atom), and returns an element of the semiring: I : U,(Pn ---+ (D" ---+ A)), where Pn is the set of n-ary predicates. The notion of interpretation can be used to associate elements of the semiring also to formulas which are more complex than ground atoms. More precisely, we can define the function value1 which takes any formula appearing in a program (not a clause) and returns an element of the semiring:

• The value associated to a non-ground atom of the form F = 3x.A(x) is computed by considering the lub of the values associated to all the ground atoms A(xjd), where d is any domain element. That is, value1(F) = lub{I(A(d)), for all dE D}. Formulas of this kind occur in SCLP languages since variables appearing in the body of a clause but not in its head are considered to be existentially quantified. For example, in the special case of logic programming the clause p (a) :- q (x, a) is just a shorthand for the formula p(a) ~ 3x.q(a, x).
• The value associated to a conjunction of atomic formulas of the form A 1\ B is the product of the values associated to A and B: value1(A 1\ B) = value1(A) x value1(B).
• For any semiring element a, value1(a) =a.

Note that the meaning associated to formulas by func­ tion value1 coincides with the usual logic program­ ming interpretation [Llo93] when considering the semir­ ing ScsP· In fact, in this case 'the ordering 5os is de­ fined by false 5os true, the lub operation of the lattice ( {true, false}, 5os) is V, and the glb is /\. Thus, for ex­ ample, value1(3x.A(x)) = lub{I(A(d)), for all dE D} = V{I(A(d)), for all dE D} . Thus it is enough that one of the A(d) is assigned the value true that the value asso­ ciated to the whole formula 3x.A(x) is true. Note also that in this special instance the lub and glb of the lat­ tice coincide with the two semiring operations, but this is not true in general (see Section 2).

Given a clause of the form H: -Band an interpreta­ tion I, we say that the clause is satisfied in I if and only if value1(H) 2: value1(B). This is consistent with the usual treatment of clauses in logic programming, where a clause is considered to be satisfied if the body logically implies the head, and by noting that logical implication in the semiring ScsP coincides with the ordering '5:scsp·

For example, the clause p(a) :- q(b) is satisfied in I if I(p(a)) 2: I(q(b)); the clause p(x) :- q(x,a) is satisfied if Vx.(I(p(x)) 2: I(q(x , a))); the clause p(a) :- q(x,a) is satisfied if I(p(a)) 2: valuei(3x.q(x,a)); the clause p(x) :- q(x,y) is satisfied if'v'x.(I(p(x)) 2: valuei(3y.q(x, y))).

An interpretation is a model for a program P if all clauses of P are satisfied in I. Given a program and all its models, one would like to identify a unique single model as the representative one. In logic programming this is done by considering the minimal model [Llo93], which is obtained by intersecting all the models of the program. This works because models in logic program­ ming are assimilable to sets of ground atoms, those with associated value true. Here we follow the same approach, but we have to generalize the notion of intersection of two models, written as "o", as their glb in the lattice (A, :S). Definition 4 (model intersection) For every ground atomic formula A and two models I1 and I2 , h oh(A) = glb(h(A), h(A)). o Theorem 5 (model intersection) Consider two models M 1 and M 2 for a CLP(S,D) program P . Then M1 o M2 is a model for P as well.

Proof: Since M; is a model for P for i = 1, 2, it must be that, for every clause H : -B, M;(B) :S M;(H) . Consider now the model M = M1 o M2 . We need to prove that, for all H : -B, also M(B) :S M(H) holds. Without loss of generality, assume that B = A1 , A2 . Thus M;(B) = M;(A1 ) x M;(A2) for i = 1, 2 and M(B) = M(Al) X M(A2) = glb(Ml(Al) , M2(Al)) X glb(M1 (A2 ), M2(A2)). Also, M(H) glb(M1(H),M2(H)). Since glb(M1 (A1 ),M2(A1 )) :S M1(AI) and glb(M1(A2),M2(A2)) :S MJ(A2) by defi­ nition of glb, and recalling that x is monotone, we have that. M(B) :S M1 (B). The same reasoning applies also for proving that M(B) :S M2 (B) . By transitivity of :S, we thus get M(B) :S M1 (H) and M(B) :S M2 (H). Since M(H) is the glb of M1 (H) and M2 (H), and since the glb of two elements if the greatest among the elements which are smaller than both, we have that M(B) :S M(H). 0

It is easy t.o see that the operation of model intersec­ tion is associative, idempotent, and commutative. Thus its application can be extended to more then two mod­ els. Given a set of models MS, we will write o(MS) as the model obtained by intersecting all models in MS.

Given a program P and the set of all its models, its minimal model is obtained by intersecting all models: MMp = o({M I M is a model for P}). The model­ theoretic semantics of a program P is its minimal model, MMp.

Consider the program P described at the end of last section. The minimal model M Mp for such a program must assign a non-positive integer to each ground atom, and it is the following function:

M Mp(t(a)) = -2

M Mp(q(a)) = -2

MMp(r(a)) = -3

MMp(p(a,c)) = -3

M Mp(p(a, b)) = -2

MMp(s(a)) = max(-2, -3) = -2

For each other atom different from the ones considered above, M Mp returns -oo.

5 Fixpoint semantics

We define now the operator Tp which extends the one used in logic programming [Llo93] by following the same approach as in the previous section. The resulting op­ erator maps interpretations into interpretations , that is, Tp: ISp--+ ISp, where ISp is the set of all interpreta­ tions for P . Given an interpretation I and a ground atom A, assume that program P contains k clauses defining the predicate in A. Clause i is of the form A : - Bl, ... , B~,. Then

This function coincides with the usual immediate conse­ quence operator of logic programming when considering the semiring Scsp.

Consider now an ordering j among interpretations which respects the semiring ordering.

Definition 6 (partial order of interpretations)

Given a program P and the set of all its interpreta­ tions ISp, we define the structure (IS, j), where for any h, h E IS, h j h if h (A) :Ss h(A) for any ground atom A. 0

It is easy to see that (IS, j) is a complete partial or­ der, whose greatest lower bound coincides with the glb operation (suitable extended to interpretations). It is also possible to prove that function Tp is monotone and continuous over the complete partial order (IS, j).

By using these properties, classical results on partial orders [Tar55] allow us to conclude that

• Tp has a least fixpoint, lfp(Tp), which coincides with glb({I I Tp(I) j I});
• the least fixpoint of Tp can be obtained by comput­ ing Tp t w. This means starting the application of Tp from the bottom of the partial order of interpre­ tations, called I 0 , and then repeatedly applying Tp until a fixpoint.

Consider again the program at the end of Section 3. We recall that in this specific case the semiring is S = (-NU {-oo},max,+,-oo,O) and D = {a,b,c}. Thus function Tp is:

In this semiring the bottom. interpretation I 0 is the in­ terpretation which maps each semiring element into itself and each ground atom into the bottom of the lattice asso­ ciated to the semiring, that is, -oo. Note that we slightly abused the notation since interpretations are functions whose domain contains only ground atoms (see Section 4), while here we also included semiring elements. This simplifies the definition of I 0 ; however, it is possible to obtain the same result with a more complex definition of I 0 which satisfies the definition of interpretation. Given I 0 , we obtain h by applying function Tp above. For ex­ ample, h(r(a)) = -3. Instead, h(p(a,c)) = -oo, and I2(p(a,c)) = h(r(a)) = -3. The following table gives the value associated by the interpretations I; with each ground atom. Some of the atoms are not listed because each interpretation I; gives them value -oo. All interpretation I; with i > 4 coincide with I4, thus I4 is the fixpoint of Tp.

The most interesting case is the computation of the value associated to s(a). In fact , h(s(a)) = max{h(p(a, a)), I2(p(a, b)), I2(p(a, c))} = max{ -oo, -oo, -3} = -3. Instead, I4(s(a)) = max{h(p(a, a)), h(p(a, b)), h(p(a, c))} = max{ -oo, -2, -3} = -2. Note that the clause s (x) :- p (x, y) is considered equivalent to all its instantiations. In particular, when x = a, we have the three clauses s (a) :- p (a, a), s (a) :- p(a, b), and s (a) :- p (a, c). These are the clauses to consider when computing I(s(a)).

We will now prove that the least fixpoint of function Tp coincides with the minimal model of program P . To do that, we need an intermediate result which shows that the models of a certain program P are the solutions of the equation Tp(I) ~ I.

Theorem 7 (models and Tp) Given any interpreta­ tion I for a program P, I is a model for P if and only ifTp(I) ~f.

Proof: Consider any ground atom H and assume there are two clauses with H as their head: H : -B1 and H : -B2. By definition of model, each clause H : -B; is satisfied in I . Thus I(H) 2: I(B;) . Now, function Tp assigns to H the sum of the values assigned by I to B1 and B2, thus Tp(I)(H) = I(Bl) + I(B2). But the + operation coincides with the lub of the semiring, thus any value of the semiring which is greated than both I(B1 ) and I(B2) is also greater than their sum. Therefore Tp(I)(H) :'::: I(H). A similar reasoning works also for proving that if Tp(I)(H) :'::: I(H) for any ground atom H then I is a model. 0

Theorem 8 (model and fixpoint semantics)

Given a SCLP{S,D) program P, we have that MMp = ljp(Tp) .

Proof: By definition of minimal model , M Mp = glb( {I I I is a model for P} ). By Theorem 7, we get M Mp = glb( {I I Tp(I) ~ I}). By the classical results cited above, this coincides with the least fixpoint of Tp. 0

6 Proof-theoretic semantics

We will define here a proof-theoretic semantics based on a resolution rule, just like in CLP [JL87). However, we need first to rewrite the program into a form which is more suitable to our semantics.

First, we rewrite each clause so that the head is an atom whose arguments are only variables. This means that we must explicitely specify the substitution that was written in the head, by inserting it in the body. That is, given a clause p( t 1 ,· . . . , tn) : - B we transform it into p(x), ... ,xn): -(B,O) where 0 = {x!/tl,···,xnftn}· Thus bodies now have the following form: B1 :: (B, 0). We recall that B can be either a collection of atoms or a value of the semiring. To give a uniform representa­ tion to bodies , we can define them as triples containing a collection of atoms (possibly empty), a substitution, and a value of the semiring (possibly, 1). Thus bod­ ies are now of the form B2 :: (LAT, 0, a). If we have a body belonging to the syntactic category B1 of the form (a,O), we get (O,O,a). If instead we have (C,O), where Cis a collection of atoms, we get (C, 0, 1). Thus clauses have now the form CLJ :: H : -B2. Initial goals need to be transformed as well: given a goal G = (: -C), where C is a collection of ground atoms, we get the goal G' = (: -(C,c, 1)). The reason why we write the empty substitution and the value 1 of the semiring is that both these elements are the unit elements w.r.t. the opera­ tions we want to perform on them, that is, composition of substitution and constraint combination.

In summary, given a SCLP(S,D) program, we get a program in an intermediate language, whose syntax is as follows:

B2 :: (LAT, 0, a)

CL1 :: H: -B2

P1 :: C£1 I C£1, P1

G1 :: B2

Consider again the example at the end of Section 3. The transformed program is then

s(x) ( p(x,y), c,O).

p(x,y)

( q(a), {x=a,y=b}, 0).

p(x,y)

( r (a) , {x=a,y=c}, 0).

q(x) ( t (a) , {x=a}, 0).

t(x)

(0, {x=a}, -2 ) .

r(x) (0, {x=a}, -3 ) .

Once we have transformed the given SCLP program into a program in the syntax just given, we can apply the following semantic rule. This rule defines the transitions of a nondeterministic transition system whose states are goals (according to the syntactic category G 1).

If the current goal contains an atom which unifies with the head of a clause, then we can replace that atom with the body of the considered clause, performing a step sim­ ilar to the resolution step in CLP. The main difference here is that we must update the third element of the goal, that is , the semiring value associated to the goal: if before the transition this value is a and the transition uses a clause whose body has value a1 , then the value associated to the new goal is a x a1 . The reason for us­ ing the x operation of the semiring is that this is exactly the operation used when accumulating constraints in the SCSP framework.

A derivation is a finite or infinite sequence of applica­ tions of the above rule. A refutation is a finite derivation whose final goal is of the form (D, 8, a) .

Let us now consider the set

S = { (C, a) I (C, c, 1) =>* (D, 8, a) for some 8}

which contains all pairs representing all refutations for the given program. Notice that we can forget about the derivation 8 accumulated during the refutations, since we assumed to always start with a ground goal. Thus 8 only refers to variables introduced during the derivation.

Now we are ready to define function OSp which, given a ground atom, returns a value of the semiring. More formally, function OSp : AT-+ A, where AT is the set of ground atoms and A is the semiring set, is defined as follows : OSp(C) = I:a,I(C,a;)ES a;. Notice that, if the set of all a; such that (C, a;) is in S is empty, OSp(C) returns the unit element for +, that is, 0.

For example, by considering the goal (s(a), c, 1), we get two refutations, one represented by the pair (s(a) , -2) , and the other one by (s(a) , -3). Thus OSp(s(a)) =max( -2, -3) = -2.

Theorem 9 (model and operational semantics)

Given a SCLP(S,D) program P, we have that M Mp = OSp.

Proof (sketch): The statement can be proved by induc­ tion on the length n of the refutations, and considering at step n the set Sn = { (C, a) I (C, c, 1) -+n (D, 8, a) and such that there is no refutation of length greater than n for (C, a)}. The proof is similar to that used in [Llo93] for logic programming, although we have to generalize because of the .presence of semiring values. D

For lack of space and sake of readability, in this paper we treated only the case of goals consisting of a ground atom. However, our results can be extended also to the general case of non-atomic and/or non-ground goals.

7 Future work

We are now studying how to efficiently implement our framework. . Techniques related to heuristically guided search can be useful to cut some paths in the search tree. However, when the partial order is not total, we may have to consider more than one path at a time, as noted in the previous section. Other techniques that we are investigating are based on dynamic programming [BMR97] or on other methods to efficiently compute the solutions in a bottom-up way.