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.