Semantics of Aggregates Date: Mon, 11 Oct 2004 From: Vladimir Lifschitz To: TAG I'd like to tell you about an important recent invention in the theory of logic programming -- an extension of the answer set semantics to programs with aggregates. It is described in the paper Wolfgang Faber, Nicola Leone and Gerald Pfeifer, "Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity". In Proceedings of the 9th European Conference on Artificial Intelligence (JELIA 2004). You can also find it online: http://www.wfaber.com/research/papers/jelia2004.pdf . Only partial solutions had been available before this publication. Now, I think, we pretty much have a complete solution. First a few words about one of those partial solutions--the semantics of weight constraints in the input language of lparse (Simons et al, "Extending and implementing the stable model semantics," Artificial Intelligence 138 (2002), 181-234; http://www.tcs.hut.fi/~ini/papers/). That language allows us to assign numbers, called weights, to atoms p_1,...,p_n, and then use expressions of the form L [p_1,...,p_n] U (L and U are numbers) in the body of a rule. Intuitively, that expression means that the sum of the weights of the atoms included in the answer set is greater than or equal to the lower bound L and less than or equal to the upper bound U. For instance, if the weights of p and q are equal to 1 then the weight constraint 1 [p,q] 1 expresses that exactly one of the atoms p, q belongs to the answer set. In the body of a rule this expression has the same meaning as the disjunction (p, not q) ; (q, not p). The semantics of weight constraints in the language of lparse works fine as long as the weights of all atoms are nonnegative. But if weights are allowed to be negative then this semantics exhibits unnatural behavior, as Paolo Ferraris and I argued in Footnote 6 to our paper "Weight constraints as nested expressions" (Theory and Practice of Logic Programming, to appear; http://www.cs.kuleuven.ac.be/~dtai/projects/ALP/TPLP/TPLP_CONTENTS/ TPLP_CONTENTS.html). We gave there an example showing that the semantics is not fully satisfactory in the case of negative weights, but we couldn't offer an acceptable alternative. What is special about the case of nonnegative weights? What makes the problem of defining the semantics of weights in this case easier? As long as all weights are nonnegative, the sum of the weights of a set of atoms is a monotone function of that set: if X is a subset of Y then the total weight of X is less than or equal to the total weight of Y. Finding the "right" semantics of aggregates without a monotonicity assumption had been an open problem until the paper by Faber, Leone and Pfeifer (I will refer to it as the FLP paper). The definition of an answer set for "traditional" logic programs is based on the concept of a reduct, and to extend that definition to a larger class of programs we need to generalize that concept. From the FLP paper we learn how to define reducts for programs with aggregates, and we learn also why inventing that generalization was not easy. It turns out that the familiar definition of the reduct needs to be modified first; once this is done, incorporating aggregates becomes straighforward. This modification is something that apparently had not occurred to anyone prior to the FLP paper. Take a program consisting of rules of the form A <- B_1,...,B_m, not C_1,..., not C_n (A,B_1,...,B_m,C_1,...,C_n are atoms). According to the usual definition, its reduct relative to a set X of atoms is constructed in two steps: (Selection) Select the rules such that C_1,...,C_n don't belong to X. (Simplification) in each of these rules, drop not C_1,..., not C_n. In the FLP paper, the selection step is modified as follows: (FLP Selection) Select the rules such that B_1,...,B_m belong to X; C_1,...,C_n don't belong to X. The authors drop the simplification step (although that is not essential-- they could have kept it, as in the original definition). Example: According to the old definition, the reduct of the program p <- not q q <- not p r <- p r <- q relative to {p,r} is p r <- p r <- q. The new definition gives p <- not q r <- p. The authors show that the difference between the two definitions is, in a sense, not important: the smallest set closed under the "old" reduct of P relative to X equals X if and only if X is a minimal set closed under the "new" reduct of P relative to X. Consequently, replacing the old definition of the reduct by new has no effect on the concept of an answer set. This little trick turned out to be a key to the problem of the semantics of aggregates. Isn't this interesting? See the paper for details. ============ Date: Mon, 11 Oct 2004 From: Nicola Leone and Wolfgang Faber To: TAG first of all, we warmly thank Vladimir for the nice words on our paper, and for his very clear presentation of a fundamental part of the work. We have slightly revised the paper, and have incorporated an improvement stimulated by an observation by Vladimir. The revised version is available online from http://www.wfaber.com/research/papers/jelia2004.pdf ============ Date: Tue, 12 Oct 2004 From: Nicola Leone To: Vladimir Lifschitz thanks a lot for your nice words on our work. We value your opinion very much, and we are therefore very happy for your positive evaluation. > In the FLP paper, the selection step is modified as follows: > Select the rules such that > B_1,...,B_m belong to X; > C_1,...,C_n don't belong to X. > The authors drop the simplification step (although that is not essential-- > they could have kept it, as in the original definition). Note that we had to drop the simplification step, because it was a source of problems for programs with aggregates. Actually, we can freely delete all *antimonotone* true literals (no matter whether they are positive or negative); but we cannot delete monotone or nonmonotone true literals (for nonmonotone literals, we mean literals like AVERAGE, which are neiter monotone nor antimonotone). Consider, for instance, the following program: a :- not count{a} < 1. [here, "not count{a} < 1" is a monotone literal.] The interpretation { a } would be an answer set if the reduct simplifies the rule and drops the true literal "not count{a} < 1". ============== Date: Tue, 12 Oct 2004 From: Vladimir Lifschitz To: Nicola Leone You are right, sometimes it does matter whether we drop simplification. But I'm wondering which alternative is better. Let's introduce an "abbreviation" b for count{a} < 1 and rewrite your program as follows: a :- not b. b :- count{a} < 1. I would expect this transformation to modify the colelction of answer sets in a "conservative" way -- if we take the answer sets for the new program and drop b from each of them then we'll get the answer sets for the original program. Does your semantics have this property? ============== Date: Tue, 12 Oct 2004 From: Nicola Leone and Wolfgang Faber To: Vladimir Lifschitz thanks a lot for your observation. These special cases are very helpful to clarify the semantics and to eliminate possible anomalies. > a :- not count{a} < 1. ----------------------- > a :- not b. > b :- count{a} < 1. ----------------------- > Does your semantics have this property? We think that the semantic misses the "unfolding" property only in a very specific case: a :- not L. where L satisfies the following 3 conditions: (i) L is an aggregate atom, and (ii) L is in recursion with a (L is an Unstratified Aggregate), and (ii) L is not monotone. We believe that, apart from this case, the "unfolding" property is always guaranteed; but we will ponder about that, and we'll try to clarify that in the long version of the paper. In order to avoid any problem, one can slightly restrict the language by forbidding that specific case (or a small class containing it). We believe that, under this restriction: 1. the "unfolding" property is preserved, and 2. it does not matter if you make the simplification step or not (coherently with your intuition on the simplification). ============== Date: Tue, 12 Oct 2004 From: Vladimir Lifschitz To: Nicola Leone and Wolfgang Faber Another option is to keep the syntax of logic programs with aggregates as currently defined, and to include the simplification step in the semantics. Then the rule a :- not count{a} < 1 will have two answer sets, just like a :- not not a when nested expressions are allowed. ============== Date: Mon, 25 Oct 2004 From: Vladimir Lifschitz To: TAG I have learned several important things from the new paper Paolo Ferraris, Answer sets for propositional theories, http://www.cs.utexas.edu/users/otto/papers/proptheories.ps . and I'd like to share with you my impressions. 1. EQUILIBRIUM LOGIC IS AS EASY TO UNDERSTAND AS ANSWER SETS. Equilibrium logic (EL), invented by David Pearce, is a nonmonotonic formalism that is an extension of logic programs under the answer set semantics (including programs with nested expressions). Syntactically, it's even simpler than logic programs, because its postulates have more uniform structure than rules in the sense of logic programming. Any propositional formula can be a postulate; a rule is simply a formula of a special form: an implication without other implications in the antecedent (body) and consequent (head). But semantically EL is somewhat complicated, or so I used to think before reading Paolo's new paper. David's definition of a model in equilibrium logic is based on Kripke models, and it doesn't look similar to the definition of an answer set. The fact (proved by David) that, in the special case when the theory is a set of rules, models in his sense are exactly answer sets, is somewhat surprising. Paolo shows us now how to give a "logic programming style" definition of an answer set for arbitrary propositional formulas, not just for rules. And he proves that answer sets in the sense of his definition are exactly models in the sense of EL, so that what he defined is not a new nonmonotonic logic; this is merely an alternative description of EL. So EL is not as different from logic programming as I used to think. Paolo's definition of an answer set is short and simple, but inventing that definition was tricky, for the same reason why it was not easy to invent the definition of an answer set for programs with aggregates proposed in the JELIA'04 paper by Faber at al (I wrote to TAG about that paper recently, see http://www.cs.utexas.edu/tag/aggregates). In both cases the difficulty is that you need to modify the traditional definition before you can generalize it. 2. EQUILIBRIUM LOGIC IS NOT JUST A TECHNICAL TOOL. I first realized that EL is important back in 1999, when David showed me how it can be used to prove strong equivalence. (That conversation has led us eventually to the TOCL paper on strong equivalence, joint with Agustin Valverde.) But EL was used then as a technical tool for answering mathematical questions, not as a knowledge representation language. From Paolo's paper we learn now that propositional formulas under the EL semantics that are, syntactically, a little more complex than rules are useful from the knowledge representation perspective. What he uses is formulas that are "almost rules": they have one extra level of implications, as in (p -> q) -> r. (1) Specifically, he shows that rules with aggregates, understood as in the JELIA paper mentioned above, can be viewed as shorthand for formulas of this kind. Treating aggregates as abbreviations, as proposed by Paolo, subsumes both the semantics of aggregates proposed by Faber et al and other useful ASP constructs, such as choice rules. Strictly speaking, the use of nested implications here can be avoided, because any propositional formula is strongly equivalent to a set of rules. This surprising fact was established independently by Pedro Cabalar and Paolo, and they are writing a joint paper about it. For instance, as I learned from them, (1) is strongly equivalent to the program r <- not p r <- q r v p v not q But eliminating nested implications is a rather complicated process (similar to converting formulas to clausal form in classical logic, but more involved), so that representing rules with aggregates by formulas with nested implications looks like a good idea. 3. NONDISJUNCTIVE PROGRAMS WITH WEIGHT CONSTRAINTS ARE SIGMA-2-P. Consider the class of nondisjunctive programs with weight constraints (Simons et al, AIJ, Vol. 138, 2002). What is the complexity of the problem of existence of an answer set for such programs? If the semantics of the language is defined as in the AIJ paper mentioned above, this problem is clearly in class NP. But what if the semantics is defined in accordance with the general theory of aggregates from the JELIA'04 paper by Faber et al? Consider, for simplicity, the case of weight constraints that don't contain negation: L [A1=w1,A2=w2,...] U (2) where A1, A2,... are aroms. In this case, the two versions of semantics are equivalent to each other whenever all weights w1, w2,... are positive. And it turns out that the difference in the case of negative weights has a significant effect on complexity! Assume that we adopted the semantics due to Faber et al (equivalent to Paolo's proposal to treat (2) as shorthand for a formula of equilibrium logic.) Paolo shows that as soon as we allow weight constraints of the form 0 [A1=1,A2=-1] (3) in the bodies of rules, the problem of existence of an answer set jumps to the next level of the polynomial hierarchy and becomes Sigma-P-2 complete, jusst as the corresponding problem for disjunctive programs. Thus nondisjunctive rules with aggregates are as "bad," computationally, as disjunctive rules. To implement them, we have to use algorithms similar to those implemented in disjunctive answer set programming systems, such as dlv and GnT. Incidentally, Paolo's semantics treats weight constraint (3) as alternative notation for the formula A2 -> A1. I find this quite intuitive: (3) says that if the answer set includes A2 then it includes A1 as well. ============== Date: Tue, 2 Nov 2004 From: Nicola Leone and Wolfgang Faber To: TAG we also liked Paolo's paper, and we would like to add some comments on the complexity issues, as we did also a finer grained complexity analysis. Incidentally, we have proved a very similar result a few weeks ago (stimulated by a question posed by Nikolay Pelov via email). Indeed, we proved that the our language (with aggregates, as described in our JELIA04 paper) remains SigmaP2-complete even if we disallow disjunction. Our proof was, however, based on a reduction from QBFs to normal logic programs with aggregates. We like very much Paolo's reduction from Disjunctive Logic Programs; it's *very* nice! We would like to point out that hardness holds only if (1) nonmonotone (i.e. neither monotone nor antimonotone) aggregates occur [note that sum with positive and negative summands is nonmonotone], and (2) aggregates occur in recursion. Both conditions above are strictly necessary for the SigmaP2-hardness. Actually, we did also a finer grained analysis, and we checked the precise complexity of some relevant subcases. If nonmonotone aggregates are not recursive, then the problem remains in NP, even if both monotone and antimonotone *arbitrary* (even recursive) aggregates are present. In other words, the language allowing *all* the following features: - arbitrary (also recursive) monotone aggregates (like SUM_> over positive integers, and SUM_< over negative integers), and - arbitrary (also recursive) antimonotone aggregates (like SUM_> over negative integers, and SUM_< over positive integers), and - stratified nonmonotone aggregates (like AVG and SUM_> over arbitrary integers), is still in NP. This observation can be useful for implementation issues, since one can still employ an NP "machinery" to implement a rather large class of aggregates (with nice semantic properties). ============== Date: Tue, 2 Nov 2004 From: Paolo Ferraris To: Nicola Leone and Wolfgang Faber thanks for the nice words. The fact that the complexity of nondisjunctive programs with stratified nonmonotone aggregates is in NP is very interesting. It is probably the case in which the semantics for weight constraints with negative weights of Simons at al, 2002, and yours coincide.