Symmetric Splitting in the General Theory of Stable Models

1 Introduction

This paper contributes to the theory of stable models, which is the mathematical basis of answer set programming (ASP) [Marek and Truszczy´nski, 1999; Niemel¨a, 1999; Lifschitz, 2008].

The splitting method [Lifschitz and Turner, 1994] can be sometimes used to reduce the task of computing the stable models of a logic program to similar tasks for smaller programs. Consider, for instance, the program

Its stable models can be generated as follows. We concentrate first on the program consisting of the first two rules of (1):

In one of its stable models, p is true and q is false; call that model M1. In the other, p is false and q is true; call it M2. Then we look at the third rule of (1) and determine how this rule instructs us to "update" each of the models M1, M2 by assigning a truth value to r. Since its body q is false in M1, the head r becomes false in this model as well. Since q is true in M2, r becomes true in M2. Thus the stable models of the given program are {p} and {q, r}.

Splitting (1) into parts is possible because r does not occur in the rules that "define" p and q, so that p and q do not "depend" on r. Accordingly, determining the truth value of r can be postponed until the time when the truth values of p and q have been determined. Program (2), on the other hand, cannot be further split in the sense of [Lifschitz and Turner, 1994], because it defines p and q in terms of each other.

A more general version of splitting is described in [Oikarinen and Janhunen, 2008]. In the framework of that paper, some atoms occurring in a logic program can be designated as its "input" atoms, and that may affect the meaning of the program. For instance, the only stable model of the one-rule program

is M1 (p is true, q is false). Intuitively, q is false in the stable model of (3) because its definition is empty: q does not occur in the head of any rule. But the program

has both M1 and M2 as its stable models, according to Oikarinen and Janhunen. Intuitively, by saying that q is an input atomwe assert that its truth value can be chosen arbitrarily; it is not supposed to be determined by the rules of the program. 1

The version of the splitting theorem established in [Oikarinen and Janhunen, 2008] allows us to split (2) into two programs: (4) andq ← not p (p is input). (5)

That theorem shows that the stable models of (2) can be characterized as the common stable models of these two one-rule programs. Since M1 is a stable model of each of the programs (4), (5), it is a stable model of (2) as well, and the same can be said about M2. This example illustrates the power of "symmetric splitting" described in [Oikarinen and Janhunen, 2008] in comparison with "top-bottom splitting" proposed in [Lifschitz and Turner, 1994]. Symmetric splitting is extended to disjunctive programs in [Janhunen et al., 2007].

The existing work on symmetric splitting does not cover, however, logic programs with variables, and it is not applicable to some types of rules that are frequently used in ASP, such as choice rules and cardinality constraints [Simons et al., 2002]. In this paper, we extend symmetric splitting to the general theory of stable models in which traditional logic programs are replaced by arbitrary first-order sentences. This general approach to stable models is introduced in [Ferraris et al., 2010] 2 and reviewed in Section 2 below. It covers the programming constructs mentioned above, and other useful constructs, by treating them as abbreviations for first-order formulas. For instance, the LPARSE programΠ consisting of three rules

1 Saying that q is an input atom is similar to augmenting the program with the LPARSE choice rule {q}. (For a description of the language of LPARSE, see http://www.tcs.hut. fi/Software/smodels/lparse.ps.)

{in(X)} :- vertex(X). :- vertex(X;Y), in(X;Y), not edge(X,Y), not edge(Y,X), X!=Y. :- {in(X):vertex(X)} n.

corresponds to the formula

where ∃nxF(x) is shorthand for

(Program Π describes large cliques in a graph, as discussed in Section 7.) Note that the first conjunctive term of (6) is logically valid, so that dropping it would not affect the class of models of (6). But the class of stable models of this formula, as defined in the next section, would be affected; in this sense, the first conjunctive term of (6) is essential. For the same reason, we do not drop ¬¬ in front of ∃n+1x.

The distinction between extensional and intensional predicates in [Ferraris et al., 2010] is similar to the distinction between input and non-input atoms in [Oikarinen and Janhunen, 2008]. As discussed below, stable models of a first-order sentence F relative to a list p of intensional predicates are defined as models of the sentence obtained from F by a certain syntactic transformation, denoted by SMp. (This transformation, like circumscription, makes a formula stronger, so that all stable models of F in the sense of that definition are indeed models of F.) For instance, if F is

(which is program (1) written as a formula) then SMpqr[F] can be equivalently rewritten as

This formula has two models-the stable models of (1).

Our version of the splitting theorem asserts that under certain syntactic conditions

2 That article is the journal version of the IJCAI-07 paper [Ferraris et al., 2007]. In the conference paper, all predicates are implicitly assumed to be intensional.

3 This is essentially the completion of (1) in the sense of [Clark, 1978]. In this example, the stable model semantics produces the same result as the completion semantics.

The example of splitting program (1) above corresponds to

To split program (2), we take

The new splitting theorem is applicable also in many situations that are not covered by the version due to Oikarinen and Janhunen, including, as we will see, some that are important from the perspective of answer set programming and knowledge representation.

The splitting theorem easily follows from a lemma that may be of interest in its own right. The lemma asserts that under certain syntactic conditions

This "splitting lemma" is more general than the splitting theorem in the sense that it is applicable, in principle, to formulas of any syntactic form, not only to conjunctions. On the other hand, it does not split the formula itself; it only splits the list of intensional predicates.

We will see that the assumption about F, p and q in the statement of the splitting lemma is related to the concept of a loop, introduced in [Lin and Zhao, 2004] for traditional logic programs and generalized to arbitrary first-order formulas in [Lee and Meng, 2008].

This paper includes proofs of the splitting lemma and the splitting theorem, and also a brief discussion of the applications of splitting that motivated this work.

2 Review: Operator SM

This review follows [Ferraris et al., 2010]. Notation: if p and q are predicate constants of the same arity then p ≤ q stands for the formula

where x is a tuple of distinct object variables. If p and q are tuples p1, . . . , pn and q1, . . . , qn of predicate constants then p ≤ q stands for the conjunction

and p < q stands for (p ≤ q) ∧ ¬(q ≤ p). In secondorder logic, we apply the same notation to tuples of predicate variables.

We will define the stable model operator with the intensional predicates p, denoted by SMp. Some details of the definition depend on which propositional connectives and quantifiers are treated as primitives, and which of them are viewed as abbreviations. We assume that

are the primitives; ¬F stands for F → ⊥, ⊤ is ⊥ → ⊥, and F ↔ G is (F → G) ∧ (G → F ).

Let p be a list of distinct predicate constants p1, . . . , pn other than equality. For any first-order sentence F, by SMp[F] we denote the second-order sentence

where u is a list of n distinct predicate variables u1, . . . , un, and F ∗ (u) is defined recursively:

• pi(t)∗ = ui(t) for any tuple t of terms;
• F ∗ = F for any atomic F that does not contain members of p;
• (F ∧G)∗ = F ∗ ∧ G∗ ;
• (F ∨G)∗ = F ∗ ∨ G∗ ;
• (F →G)∗ = (F ∗ → G∗ ) ∧ (F → G);
• (∀xF)∗ = ∀xF ∗ ;
• (∃xF)∗ = ∃xF ∗ .

A model of F is stable (relative to the set p of intensional predicates) if it satisfies SMp[F].

For instance, let F be the formula

representing the choice rule

If we take q to be the only intensional predicate then F ∗ (u) is

so that SMq[F] is

This sentence is equivalent to the first-order formula

which reflects the intuitive meaning of choice: q is an arbitrary subset of p.

3 Splitting Lemma

The statement of the splitting lemma refers to the predicate dependency graph of a formula, defined in [Ferraris et al., 2007] and [Ferraris et al., 2010]. 4 This definition, reproduced below, generalizes the idea that if a logic program contains, say, the rule

then p "positively depends" on q in this program.

Recall that an occurrence of a predicate constant, or any other subexpression, in a formula is called positive if the number of implications containing that occurrence in the antecedent is even, and strictly positive if that number is 0. We say that an occurrence of a predicate constant in a formula is negated if it belongs to a subformula of the form ¬F (that is, F → ⊥), and nonnegated otherwise. For instance, in the formula

4 We follow here the version given in the second paper, which is simpler but can introduce some unnecessary dependencies when applied to deeply nested implications.

corresponding to rule (10), both p and r are positive, p is strictly positive, and r is negated.

A rule of a first-order formula F is a strictly positive occurrence of an implication in F. For instance, the rules of (8) are p(x) → (q(x) ∨ ¬q(x)) and ¬q(x); the only rule of (11) is (11) itself.

For any first-order formula F, the predicate dependency graph of F (relative to the list p of intensional predicates) is the directed graph that

• has all intensional predicates as its vertices, and
• has an edge from p to q if, for some rule G→H of F,
• p has a strictly positive occurrence in H, and
• q has a positive nonnegated occurrence in G.

For instance, the predicate dependency graph of (11) relative to pqr has one edge, from p to q. We will denote the predicate dependency graph of F relative to p by DGp[F ].

Splitting Lemma, Version 1 Let F be a first-order sentence, and let p, q be disjoint tuples of distinct predicate constants. If each strongly connected component of DGpq[F ] is a subset of p or a subset of q then

Note that the condition on DGpq[F] in the statement of the lemma holds trivially if all strongly connected components of this graph are singletons.

Example 1: F is ¬p ∧ r → q, p is p, q is q. In this case, the graph DGpq[F ] has two vertices p, q, and no edges, so that its strongly connected components are singletons. The splitting lemma asserts that

is equivalent to the conjunction of

and

Each of these three expressions can be rewritten as a propositional formula using the methods described in [Ferraris et al., 2010]. Formula (12) becomes

(13) becomes

and (14) turns into

It is clear that (15) is indeed equivalent to the conjunction of (16) and (17).

Example 2: F is r → p ∨ q, p is p, q is q. The graph DGpq[F] is the same as in Example 1, and the splitting lemma asserts that

is equivalent to the conjunction of

and

The methods for simplifying SMp[F ] described in [Ferraris et al., 2010] are not directly applicable to (18), but they allow us to simplify (19) and (20). The version of program completion presented in that paper turns the former into p ↔ ¬q ∧ r and the latter into q ↔ ¬p∧r. Consequently (18) is equivalent to the conjunction of these two formulas.

Example 2 shows that the splitting lemma allows us to expand the power of completion, as a method for describing stable models, to some disjunctive programs. This is similar to the generalization of completion to disjunctive programs described in [Lee and Lifschitz, 2003]; the advantage of the splitting lemma is that it is applicable to programs with variables. For instance, using the same argument as in Example 2 we can check that

is equivalent to the conjunction of

and

To illustrate the role of the condition on the predicate dependency graph in the statement of the splitting lemma, take F to be p ↔ q, with p as p and q as q. The graph DGpq[F] in this case has two edges, from p to q and from q to p. The strongly connected component {p, q} of this graph has a common element with p and a common element with q, so that the splitting lemma is not applicable. Accordingly, the formulas SMpq[p ↔ q] and SMp[p ↔ q] ∧ SMq[p ↔ q] are not equivalent to each other. Indeed, the former can be rewritten as ¬p ∧ ¬q, and each conjunctive term of the latter is equivalent to p ↔ q.

The splitting lemma as stated above can be equivalently reformulated as follows:

Splitting Lemma, Version 2 Let F be a first-order sentence, and let p be a tuple of distinct predicate constants. If c1 , . . . , cn are all the strongly connected components of DGp[F] then

A loop of a first-order formula F (relative to a list p of intensional predicates) is a nonempty subset l of p such that the subgraph of DGp[F] induced by l is strongly connected. It is clear that the strongly connected components of DGp[F] can be characterized as the maximal loops of F .

Splitting Lemma, Version 3 Let F be a first-order sentence, and let p be a tuple of distinct predicate constants. If l1 , . . . , ln are all the loops of F relative to p then

The last two versions of the splitting lemma are equivalent to each other in view of the fact that the operator SMp is monotone with respect to p: if p contains q then SMp[F] entails SMq[F ].

4 Proof of the Splitting Lemma

Lemmas 1 and 2 below can be easily proved by induction [Ferraris et al., 2010].

is logically valid.

About a formula F we say that it is negative on a tuple p of predicate constants if members of p have no strictly positive occurrences in F .

Lemma 2 If F is negative on p then

is logically valid.

The following lemma extends Lemma 3 from [Ferraris et al., 2006] to first-order formulas.

Lemma 3 Let p1, p2 be disjoint lists of distinct predicate constants, and let u1, u2 be disjoint lists of distinct predicate variables of the same length as p1, p2 respectively.

• (a) If every positive occurrence of every predicate constant from p2 in F is negated then

is logically valid.

• (b) If every nonpositive occurrence of every predicate constant from p2 in F is negated then

is logically valid.

Proof. Both parts are proved simultaneously by induction on F. Consider the case when F is G → H; the other cases are straightforward. Then F ∗ (u1, u2) is

(a) Every nonpositive occurrence of every predicate constant from p2 in G is negated, and so is every positive occurrence of every predicate constant from p2 in H. By the induction hypothesis, it follows that the formulas

are logically valid. Assume (u1, u2) ≤ (p1, p2),

and G∗ (u1, u2). By (22), we conclude G∗ (u1, p2). Then, by (24), we conclude H∗ (u1, p2). Then, by (23), we conclude H∗ (u1, u2). (b) Similar.

The following assertion is a generalization of Lemma 5 from [Ferraris et al., 2006].

Lemma 4 Let p1, p2 be disjoint lists of distinct predicate constants such that DGp1p2 [F] has no edges from predicate constants in p1 to predicate constants in p2, and let u1, u2 be disjoint lists of distinct predicate variables of the same length as p1, p2 respectively. Formula

is logically valid.

Proof. By induction on F. Consider the case when F is G → H, so that F ∗ (u1, u2) is (21); the other cases are straightforward. Assume (u1, u2) ≤ (p1, p2) and F ∗ (u1, u2). Our goal is to prove

Assume G∗ (u1, p2). By Lemma 1, the formula

is logically valid. Consequently, from the assumptions above we can conclude G, and, by (21), H. Case 1: H is negative on p1. It follows from Lemma 2 that the formula

is logically valid, and we can conclude that H∗ (u1, p2). Case 2: H is not negative on p1, that is to say, H contains a strictly positive occurrence of a predicate constant from p1. Then every positive occurrence of every predicate constant from p2 in G is negated, because otherwise there would exist an edge from p1 to p2 in DGp1p2 [F]. By Lemma 3(a), the formula

is logically valid. Consequently from the assumptions above we can conclude that G∗ (u1, u2). By (21), it follows that H∗ (u1, u2). Since every edge in DGp1p2 [H] belongs to DGp1p2 [F], by the induction hypothesis applied to H, the formula

is logically valid. We can thus conclude that H∗ (u1, p2).

Lemma 5 For any formula F and any nonempty set Y of intensional predicates, there exists a subset Z of Y such that

• (a) Z is a loop of F, and
• (b) the predicate dependency graph of F has no edges from predicate constants in Z to predicate constants in Y \Z.

The proof is essentially the same as the proof of Lemma 4 in [Ferraris et al., 2006].

Proof of Version 3 of the Splitting Lemma. It is sufficient to prove the logical validity of the formula

where each ui is the part of u that corresponds to the part li of p, and ˜ ui is the list of symbols obtained from p by replacing every intensional predicate p that belongs to li with the corresponding predicate variable u. Right to left: Clear. Left to right: Assume ∃u((u < p)∧F ∗ (u)) and take u such that (u < p)∧F ∗ (u). Consider several cases, each corresponding to a nonempty subset Y of p. The assumption characterizing each case is that u < p for each member p of p that belongs to Y , and that u = p for each p that does not belong to Y . By Lemma 5, there is a loop li of F that is contained in Y such that the dependency graph has no edges from predicate constants in li to predicate constants in Y \li . Since li is contained in Y , from the fact that u < p for each p in Y we can conclude that

Let u′ be the list of symbols obtained from p by replacing every member p that belongs to Y with the corresponding variable u. Under the assumption characterizing each case, u = u′ , so that F ∗ (u) ↔ F ∗ (u′ ). Consequently, we can derive F ∗ (u′ ). It follows from Lemma 4 that the formula

˜

is logically valid, so that we further conclude that F ∗ ( ˜ ui ). In view of (26), it follows that ∃ui ((ui < li ) ∧F ∗ ( ˜ ui )).

5 Application: Dropping Double Negations

The semantics of the answer set programming language RASPL-1 is defined in [Lee et al., 2008] using a syntactic translation that turns every RASPL-1 program into a firstorder sentence, called its FOL-representation. An answer set of a RASPL-1 program Π is defined as an arbitrary Herbrand stable model of the FOL-representation of Π.

To relate RASPL-1 to cardinality constraint programs in the sense of [Syrj¨anen, 2004], the authors defined a class of strongly regular RASPL-1 programs. The answer sets of any program in this class are identical to its answer sets in the sense of Syrj¨anen [Lee et al., 2008, Proposition 5]. This fact is stated in the paper without proof, and the key part of the proof involves checking that, under certain conditions, dropping a double negation from a first-order sentence does not affect its stable models. One such case is described in the following proposition:

Theorem on Double Negations Let H be a sentence, F a subformula of H, and H- the sentence obtained from H by inserting ¬¬ in front of F. If F is contained in a subformula G of H that is negative on p then SMp[H-] is equivalent to SMp[H].

Proof. Let G- be the formula obtained fromG by inserting ¬¬ in front of F. By Lemma 2, the formulas

and

are logically valid. Consequently

is logically valid also, and so is

It follows that SMp[H-] is equivalent to SMp[H].

By itself, this theorem does not help us prove Proposition 5 from [Lee et al., 2008]: the condition

F is contained in a subformula G of H that is negative on p

turns out to be too restrictive. What we need to observe is that this condition can be relaxed as follows:

for every strongly connected component c of DGp[H], F is contained in a subformula G of H that is negative on c.

The possibility of strengthening the theorem on double negations in this way is immediate from Version 2 of the splitting lemma.

6 Splitting Theorem

Recall that a formula F is said to be negative on a tuple p of predicate constants if members of p have no strictly positive occurrences in F (Section 4). The importance of this class of formulas for the theory of stable models is that they are analogous to constraints in traditional answer set programming: SMp[F ∧ G] is equivalent to SMp[F] ∧ G whenever G is negative on p [Ferraris et al., 2010].

Splitting Theorem Let F, G be first-order sentences, and let p, q be disjoint tuples of distinct predicate constants. If

• each strongly connected component of DGpq[F ∧G] is a subset of p or a subset of q,
• F is negative on q, and
• G is negative on p

then

Proof. By the splitting lemma, SMpq[F ∧G] is equivalent to

Since G is negative on p, the first conjunctive term can be rewritten as

Similarly, the second conjunctive term can be rewritten as

It remains to observe that the second conjunctive term of each of the formulas (27), (28) is entailed by the first conjunctive term of the other.

7 Application: Abstract ASP Programs

The intuition behind the rules of the program Π from the introduction is easy to explain. The first rule says that the extent of the predicate in is an arbitrary set of vertices. The second rule expresses the definition of a clique: a clique may not contain a pair of distinct vertices that are not adjacent to each other. The third rule expresses a restriction on the size of the clique: it is not allowed to be ≤ n.

The claim that Π describes large cliques in a graph can be made precise in two ways: by considering logic programs obtained from Π by adding descriptions of specific graphs, and in an abstract way, as a theorem about program Π itself. In both formulations below, σ is the signature consisting of the predicate constants vertex, edge, and in, and Γ is an arbitrary finite directed graph.

Correctness of Π, Formulation 1. Extend σ by adding the vertices of Γ as object constants. Let I be an interpretation of the extended signature that interprets each object constant as itself, interprets vertex as the set of vertices of Γ, and interprets edge as the set of edges of Γ. Let X be the set of ground atoms that contain vertex or edge and are satisfied by I. The following conditions are equivalent:

• I is a stable model of the conjunction of (6) and the atoms X, with the intensional predicates vertex, edge, and in,
• the extent of in in I is a clique in Γ, and its cardinality is > n.

Correctness of Π, Formulation 2. Let I be an interpretation of σ that interprets vertex as the set of vertices of Γ, and interprets edge as the set of edges of Γ. The following conditions are equivalent:

• I is a stable model of (6) with the intensional predicate in,
• the extent of in in I is a clique in Γ, and its cardinality is > n.

The correctness of Π in the sense of Formulation 2 is immediate from the fact that the result of applying the operator SMin to (6) can be equivalently written as

This fact is easy to verify using the methods of [Ferraris et al., 2010]. Formulation 1 follows from Formulation 2 by the splitting theorem, with (6) as F, the conjunction of the atoms X as G, in as p, and vertex,edge as q.

The advantage of Formulation 1 is that it describes what happens when we actually use Π to find a large clique in a graph: we run an answer set solver on a program obtained from Π by adding the definition of the graph as a set of facts. The advantage of the "abstract" Formulation 2 is that it is easier to state and to prove. The splitting theorem can be used to establish a relationship between these two kinds of correctness theorems.

8 Application: Relationship between Two Formulations of the Event Calculus

Theorem 1 from [Kim et al., 2009] shows that circumscriptive event calculus [Shanahan, 1997] can be reformulated in terms of the stable model semantics in the form

The splitting theorem stated above is used there to show that this formula can be equivalently written using a single application of the operator SM:

SMInitiates,Terminates,Releases,Happens[Σ ∧ Δ ∧ Ξ].

A further transformation is shown in [Kim et al., 2009] to turn the conjunction Σ ∧ Δ ∧ Ξ into a logic program that can be processed by existing answer set solvers.

9 Conclusion

The splitting lemma and the splitting theorem proved in this note appear to be valuable mathematical tools. The former helped us extend program completion to some disjunctive programs, including programs with variables, and to compare two approaches to the semantics of aggregates in ASP. The latter can be used to relate "abstract" ASP programs to programs containing specific facts and to turn one of the formulations of the event calculus into an executable ASP program. We hope that future work will bring us new applications of splitting to answer set programming and knowledge representation.

Acknowledgements

We are grateful to Michael Gelfond, Tomi Janhunen and Emilia Oikarinen for useful discussions related to the topic of this paper. This work was partially supported by the National Science Foundation under Grants IIS-0712113 and IIS0839821.