Bidirectional Answer Set Programs with Function Symbols
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 765-770.
© 2009 International Joint Conferences on Artificial Intelligence
Abstract
Current Answer Set Programming (ASP) solvers largely build on Datalog, which, unlike general logic programming, lacks function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e.g., lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive, but yet decidable, language that is useful, e.g., for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and some of their subclasses, addressing the main reasoning tasks. Our results also show that the recently introduced FDNC programs can be extended by inverse rules while retaining decidability, but computational costs are unavoidably higher.Thomas Eiter, Mantas Simkus
- [Baral, 2002] C. Baral. Knowledge Representation, Reasoning and Declarative Problem Solving. CUP, 2002.
- [Baselice et al., 2007] S. Baselice, P. A. Bonatti, and G. Criscuolo. On finitely recursive programs. In ICLP-07, LNCS 4670, pp. 89-103. Springer, 2007.
- [Bonatti, 2004] P. A. Bonatti. Reasoning with infinite stable mod- els. Artif. Intell., 156(1):75-111, 2004. IJCAI
- [Calimeri et al., 2008] F. Calimeri, S. Cozza, G. Ianni, and N. Leone. Computable functions in ASP: Theory and implemen- tation. In ICLP-08, LNCS 5366, pp. 407-424. Springer, 2008.
- [Chomicki and Imielinski, 1993] J. Chomicki and T. Imielinski. Fi- nite representation of infinite query answers. ACM Trans. Database Syst., 18(2):181-223, 1993.
- [Gelfond and Lifschitz, 1991] M. Gelfond and V. Lifschitz. Clas- sical negation in logic programs and disjunctive databases. New Gen. Comput., 9(3/4):365-386, 1991.
- [Heymans, 2006] Stijn Heymans. Decidable Open Answer Set Pro- gramming. Ph.D. Dissertation. Vrije Universiteit Brussel, 2006.
- [Marek et al., 1994] W. Marek, A. Nerode, and J. Remmel. The Stable Models of a Predicate Logic Program. Journal of Logic Programming, 21(3):129-153, 1994.
- [Minker, 1988] J. Minker (ed). Foundations of Deductive Data- bases & Logic Programming. Morgan Kaufm., 1988.
- [Simkus and Eiter, 2007] M. Simkus and T. Eiter. FDNC: De- cidable non-monotonic disjunctive logic programs with function symbols. In LPAR-07, LNCS 4790, pp. 514-530. Springer, 2007.
- [Syrjänen, 2001] T. Syrjänen. Omega-restricted logic programs. In LPNMR-01, LNCS 2173, pp. 267-279. Springer, 2001.
- [Thomas, 1990] W. Thomas. Automata on infinite objects. In Handbook of Theor. Comp. Sci. (B), pp. 133-192. Elsevier, 1990.
- [Vardi, 1998] Moshe Y. Vardi. Reasoning about the past with two- way automata. In Proc. ICALP-98, LNCS 1443, pp. 628-641.
- [Woltran, 2005] S. Woltran. Answer Set Programming: Model ap- plications and proofs-of-Concept. Available at http://www. kr.tuwien.ac.at/projects/WASP/report.html. Link
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
In the last decade, Answer Set Programming (ASP) has become an important paradigm of Knowledge Representation and Reasoning [Baral, 2002]. ASP, with its roots in logic programming and databases, is based on logic programs with non-monotonic negation under the answer set semantics [Gelfond and Lifschitz, 1991], and is especially wellsuited to represent problems involving common-sense reasoning. Supported by efficient reasoners, 1 ASP has been fruitfully applied in many areas of computer science and AI, including information integration, diagnosis, configuration management, reasoning about actions and change, etc. (see e.g. [Woltran, 2005] for a showcase and more details).
Current ASP implementations largely build on logic programming without function symbols. For this reason, the answer sets (also known as stable models) of an ASP program P are always finite relational structures over the relations and constants of P. This intrinsic finiteness is an acknowledged limitation in terms of expressiveness, and becomes apparent when modeling concepts that cannot be confined using a finite number of constants; this includes time, action sequences, recursive data structures like lists, and infinite processes and objects in general [Bonatti, 2004; Calimeri et al., 2008].
∗This work has been partially supported by the Austrian Science Fund (FWF) grants P20840 and P20841, and the EC project OntoRule (IST-2009-231875).
1 See http://asparagus.cs.uni-potsdam.de/
Using function symbols, we can easily generate infinite domains, and so more compactly represent problems involving infinite objects. Unfortunately, an unrestricted use of function symbols makes ASP highly undecidable. In fact, already inference from Horn logic programs becomes undecidable, and equipped with negation under the answer set semantics, it is at the second level of the analytical hierarchy (as stable model existence is Σ11-complete, cf. [Marek et al., 1994]). This immense complexity, which discouraged many researchers, has two reasons. Firstly, function symbols make the Herbrand universe infinite, and the program can have infinitely many and possibly infinite answer sets. Secondly, each answer set of a program satisfies a minimality property that quantifies over (possibly infinitely many and infinite) interpretations.
The need to represent problems with infinite domains led several authors to identify fragments of ASP with function symbols that have lower complexity; the majority of them tailored conditions for the program dependency graph [Baselice et al., 2007; Syrj¨anen, 2001; Bonatti, 2004; Calimeri et al., 2008]. While many of the identified program classes are decidable, a weakness of this approach is that recognizing the programs from such classes may be difficult, if not undecidable. Moreover, many classes allow only finite models.
The recent FDNC programs [Simkus and Eiter, 2007], avoid the above limitations. Inspired by modal fragments of first-order logic where purely syntactic conditions yield decidability, FDNC is tailored to ensure tree-shaped stable models, and allow to inductively describe infinite objects. However, e.g., in reasoning about actions, they allow to talk naturally about the future, but not the past; in FDNC programs, atoms cannot be derived from structurally more complex atoms; e.g., in the famous Yale Shooting domain, a rule Dead(x) ∨Loaded(x)←Dead(shoot(x)) is forbidden.
In this paper, we present bidirectional (BD)-programs, which are a close relative of FDNC, but are relieved from the above restriction on atom dependency direction. This makes talking about both the future and the past possible. Furthermore, in contrast to FDNC, it allows us to elegantly express eventuality conditions (A holds for some term) by backward propagation (which is not succinctly possible in FDNC), and to represent combinations of backward and forward reasoning; this makes BD-programs more expressive (and complex) than FDNC in general. Briefly, our main contributions are:
- We introduce the class of BD-programs with function symbols. Its syntactic restrictions, which modularly apply on the rules and are easy to test, ensure that the stable models of a program, like of FDNC programs, are tree-shaped. However, due to the minimality of stable models, bidirectionality of atom dependencies makes recognizing such models much more complicated, and needs special treatment.
- We thus provide a semantic characterization of stable models of BD-programs in terms of specially labeled trees. Based on it, we present algorithms for the basic reasoning tasks, including consistency testing, and brave/cautious entailment of ground/existential queries. The algorithms are different from those for FDNC; we use automata-theoretic methods and, for disjunctive programs, a suitable automata acceptance notion to obtain optimal complexity results.
- We tightly characterize the complexity of BD-programs and some of its subclasses. Under bounded predicate arities, the aforementioned reasoning tasks are 2EXPTIME-complete for disjunctive BD-programs (hence provably harder than in FDNC), but EXPTIME-complete if disjunction is disallowed; on the other hand, already brave reasoning from disjunctive BD-programs without negation is 2EXPTIME-hard. If only one function symbol is available (which suffices to model time), the complexity of reasoning drops to EXPSPACE in the disjunctive case, and to PSPACE if disjunction is disallowed.
The high expressivity of BD-programs makes them a possible host for encoding problems with matching complexity into ASP with function symbols. Examples are planning problems (e.g., conditional planning) or reasoning tasks in Description Logics (e.g., answering conjunctive queries in SHIQ and satisfiability testing in SRIQ) that are 2EXPTIME-complete, or deciding datalog query containment (3EXPTIME-complete for pairs of non-recursive and recursive queries). To our knowledge, no ASP classes, as simple as BD-programs, with similar capacity were identified before.
2 Preliminaries
Answer Set Programming We assume a standard first-order language with distinct, countably infinite sets of variables, constants, and function and predicate symbols of positive arity. A literal is either an atomA (positive literal), or a negated atom not A (negative literal).
A disjunctive logic program (briefly, program) is an arbitrary set of (disjunctive) rules r of the form
where n+m>0, all Ai are atoms (called head atoms) and all Lj are literals (called body literals). We let head(r) = {A1, . . . , An} and denote by body+(r) (resp., body-(r)) the set of atoms that occur in positive (resp., negative) body literals of r. The rule r is a fact, if m=0; a constraint, if n=0; normal, if n=1; positive, if body-(r)=∅ (we then let body(r)= body+(r)); and safe, if all variables in r occur in body+(r)).
A program P is positive (normal, etc.), if all its rules are positive (normal, etc.). The Herbrand universe HU P , Herbrand base HBP and the grounding Ground(P) of P are as usual (cf. [Minker, 1988]). By MM(P) we denote the set of ⊆-minimal (Herbrand) models of P (viewing not as classical negation).
Recall that an interpretation I is a stable model of P , iff I ∈ MM(P I ), where P I is the reduct of P w.r.t. I [Gelfond and Lifschitz, 1991]. We denote by SM(P) the set of all stable models of P. A programP is consistent, if SM(P) ̸= ∅.
An existential query q is of the form ∃⃗x.A(⃗y), where A is an n-ary predicate symbol, ⃗y is an n-tuple of variables and constants, and ⃗x is a list of all variables in ⃗y. If ⃗x is empty, then q is a ground query. A program P bravely (resp., cautiously) entails q, in symbols P |=b q (resp., P |=c q), if some (resp., every) I ∈ SM(P) contains a ground instance A(⃗t) of A(⃗x).
Alternating Tree Automata For an introduction to automata on infinite trees, we refer to [Thomas, 1990]. We here recall 2-way alternating tree automata from [Vardi, 1998].
An infinite tree T is any prefix-closed set of words over the positive integers (denoted by N), i.e., T ⊆ N∗ such that x·c ∈ T , where x ∈ N∗ and c ∈ N, implies x ∈ T . T is full if, additionally, x·c′ ∈ T for all 0<c′ <c. Each element x ∈ T is a node of T , where ϵ (the empty word) is the root of T . The nodes x·c ∈ T , where c ∈ N, are the successors of x. By convention, x·0 = x and (x·i)·(-1) = x (note that ϵ·(-1) is undefined). T is k-ary if it is full and each node in T has k successors. An infinite path in T is a prefix-closed node set p ⊆ T such that for every i ≥ 0 there is a unique x∈p such that |x| = i. A labeled tree over an alphabet Σ is a tuple (T,L), where L : T → Σ, i.e., a tree where the nodes are labeled with symbols from Σ.
For a set V of propositions, let B(V ) be the set of all Boolean formulas that can be built from V ∪ {true, false} using ∨ and ∧ as connectives. We say that I ⊆V satisfies ϕ∈B(V ), if assigning true to each p ∈ I and false to each p ∈ V \ I makes ϕ true.
Let [k] = {-1, 0, 1, . . . , k}. A two-way alternating tree automaton (2ATA) over infinite k-ary trees is a tuple A = 〈Σ, Q, δ, q0, F 〉, where Σ is an input alphabet, Q is a finite set of states, δ : Q×Σ → B([k]×Q) is a transition function, q0 ∈ Q is an initial state, and F specifies an acceptance condition. We consider here parity acceptance, which is given by a chain F : G1 ⊆ G2 ⊆ . . . ⊆ Gm of subsets of Q where Gm=Q.
Informally, a run of a 2ATA A over a labeled tree (T,L) is a tree Tr where each node n∈Tr is labeled with (x, q)∈ T ×Q. Here n describes a copy of A that is in state q and reads the node x∈T , and the labeling of its successor nodes must obey the transition function. Formally, a run (Tr, r) is labeled tree over Σr = T ×Q, which satisfies the following:
- ϵ ∈ Tr and r(ϵ) = (ϵ, q0).
- For each y ∈Tr, with r(y)=(x, q) and δ(q,L(x))=ϕ, there is a set S={(c1, q1), . . . , (cn, qn)}⊆[k]×Q such that (i) S satisfies ϕ, and (ii) for all 1 ≤ i ≤ n, we have that y·i ∈ Tr, x·ci is defined, and r(y·i) = (x·ci, qi).
A run (Tr, r) is accepting, if every infinite path p⊆Tr satisfies F as follows. Let inf(p) be the set of states q ∈Q that occur infinitely often in p. Then p satisfies F, if an even i exists for which inf(p) ∩Gi ̸=∅ and inf(p) ∩Gi-1 =∅.
An automaton accepts a labeled tree, if there is a run that accepts it. By L(A) we denote the set of trees that A accepts.
3 Bidirectional Programs
We now introduce bidirectional programs (BD-programs). After defining the full language, we focus on core programs, for which we give an algorithm for consistency checking. Other basic reasoning tasks and reasoning for the full language can be reduced to this problem.
BD-programs are syntactically restricted to ensure that stable models are tree-shaped. This allows us to recognize the possibly infinite stable models using a tree automaton.
Definition 3.1. (t-atom) An atomR(t, s1, . . ., sn) is called a t-atom, if each si is either a constant, or a variable that is distinct from and not occurring in t.
Example 3.1. Let x, y, z be variables, and c, d be constants. Then R(x, c, d, y) is an x-atom, and P(f(x), c, d, y) is an f(x)-atom. However, R(g(x), z, x) is not a g(x)-atom because x is a subterm of g(x) and x is occurs in the 3rd position of the atom. Also, R(x, c, d, f(y)) is not an x-atoms because functional terms are allowed in the first position only.
Definition 3.2. (BD-programs) Let c be a designated constant. A BD-program P consists of safe rules r of the form (1) such that, for some variable x, each atom in r is a t-atom where either t = x, t = f(x) for some unary f , or t = c.
Example 3.2. E.g., rules R(x, z, y)←P(f(x), y, z) and P (f (x), c, y) ←P (x, z, y), not R(g(x), y) are allowed in the syntax of BD-programs. However, R(f(y), x)←P(f(x), y) is not allowed since it does not fulfill the requirement above.
Observe that the rule in the introduction satisfies the above condition, and hence is allowed in BD-programs.
Note also that every atom in a stable model I of a BDprogram P is of the form R(t, c1, . . ., cn), where c1, . . ., cn are constants and t is of the form fn(. . .f1(c). . .). Observe also that the set of all terms fn(. . .f1(c). . .) forms a tree with root c, where a node f(t) is a child of t. Thus, any I can be seen as a labeled tree in which each R(t, c1, . . ., cn) ∈ I is associated to the node t.
We consider next a program which is a safe variant of a program in [Baselice et al., 2007], originally due to F. Fages.
Example 3.3. Let P consist of the rules
Then P is a BD-program, but is not finitely recursive according to [Baselice et al., 2007]: indeed, due to (3), Q(c) depends on infinitely many atoms Q(f(c)), Q(f(f(c))), . . .
Observe that P is inconsistent. Indeed, any model I of P I , by (1) and (2), must contain D(t) for each ground term t ∈ HU P . Then, by the rules (3) and (4), I must also contain Q(t) for each ground term t ∈ HU P . Hence, P I contains only instances of rules (1)-(3), and thus I is not a minimal model of P I .
If we replace (4) by Q(x)∨Q′ (x)←D(x), not Q(f(x)), we obtain a consistent program with one stable model In for each natural number n: In consists of Q(f i (c)) for each i<n, Q′ (f i (c)) for each i≥n, and D(f i (c)) for each 0≤i.
To ease the development of algorithms, we focus on core programs over unary predicates, which are described next.
Definition 3.3. (Core programs) A BD-program P is a core program, if it consists of core rules, which have the form:
- A(c) ← , where c is the special constant,
- A(f(x)) ←B(x), called f-forward rule,
- A(x) ←B(f(x)), called f-backward rule, or
- A1(x) ∨ . . . ∨ Am(x) ← [not] B1(x), . . . , [not] Bn(x), called local rule ([not] stands for a possible negation).
Core programs are structurally simple, but as expressive as full BD-programs: by a structural transformation, we can reduce consistency of a BD-program P to consistency of a core program P ′ . First, by exploiting the restricted variable interaction (see Definition 3.2), P can be translated into a BDprogram over unary predicates, arriving at rules with atoms of the form A(x), A(f(x)), and A(c) only (if predicate arities are bounded, the translation is polynomial). The resulting program can then be easily simulated by core rules.
Proposition 3.1. Under bounded predicate arities, a disjunctive (resp., normal) BD-program P can be transformed in polynomial time into a disjunctive (resp., normal) core program P ′ such that P is consistent iff P ′ is consistent.
We note that the translation moreover establishes a 1-1 correspondence between the stable models of P and P ′ .
4 Consistency in Normal BD-Programs
In this section, we develop an algorithm for testing consistency of normal core programs. To this end, we first introduce the notion of a block tree: a labeled tree that encodes a positive disjunction-free programwith an interpretation for it. We then define minimal block trees, which are the ones where the encoded interpretation coincides with the least model of the encoded program, and define an automaton recognizing such trees. To decide consistency of normal core programs, we then focus on block trees where the encoded program equals the Gelfond-Lifschitz reduct w.r.t. the encoded interpretation.
4.1 Minimal Block Trees
(Minimal) block trees are trees labeled by blocks which intuitively consists of two parts: a set of predicate names and a set of rules associated to the node.
Definition 4.1. (Block) A block is any tuple b=(α,D,R), where α is a constant or a function symbol, D is a set of unary predicates, and R is a set of positive disjunction-free core rules such that: (i) if α is a constant, then R has no fbackward rule for any function f, and (ii) if α is a function symbol f , then for each g-backward rule in R we have g = f . In case (i), b is a root block, and in case (ii) b is a child block.
Intuitively, a root block can be used as a root of the tree and a child block inside the tree. We next illustrate conditions (i-ii).
Example 4.1. Consider the following 3 blocks:
Note that b1 is a root block, b2, b3 are child blocks; b1 has 2 forward rules, b2 has a backward rule, and that b3 has no rules.
To ease the presentation, we assume that each function symbol f is indexed by i(f), that the function i is bijective, and w.l.o.g. that the set of indices of all functions in any set B of blocks is an initial segment of the positive integers.
Definition 4.2. (Block tree) Let B be a block set where k function symbols occur. Then a B-tree is any k-ary Blabeled tree T =(T,L) satisfying the following properness conditions: (i) L(ϵ) is a root block, and (ii) for all x·c∈T , L(x·c)=(α,D,R) is a child block with i(α)=c.
Example 4.2. (Cont'd) Assume i(f)=1 and i(g)=2, and B={b1, b2, b3, bf , bg} with bf = (f, ∅, ∅) and bg =(g, ∅, ∅). Take a 2-ary tree T with labeling L(ϵ)=b1, L(1)=b2, L(2)=b3, L(y)=bf for all y∈T with y=x′ ·1 and x′ ̸=ϵ, and L(y)=bg for all y∈T with y=x′ ·2 and x′ ̸=ϵ. Then T =(T,L) is a B-tree. Another B-tree T ′ can be obtained, e.g., by setting L(11)=b2 instead of L(11)=bf .
To obtain the encoded interpretation and program, we first translate nodes of trees to terms. To this end, let x = k1· · ·kn be a word over N. Then term(x) = fn(. . . f1(c) . . .), where i(fj) = kj for every j ∈ {1, . . . , n} (note that term(ϵ) = c).
Definition 4.3. (Associated interpretation) For a B-tree T = (T, L), we define its associated interpretation int(T ) as
Example 4.3. (Cont'd) Observe that int(T ) = {A(c), C(c), B(f(c)), D(g(c))} and int(T ′ ) = int(T ) ∪ {B(f(f(c)))}.
Definition 4.4. (Associated program) Let r↓t denote the grounding a one-variable rule by a ground term t. Then for a B-tree T =(T,L) its associated program prog(T ) is the smallest program closed under the following rules:
- if x ∈ T , L(x)=(α,D,R), r ∈ R, and r is a local or a forward rule, then r↓term(x) ∈ prog(T );
- if x ∈ T , L(x)=(α,D,R), r ∈ R, r is a backward rule, and x = y·c with c ∈ N, then r↓term(y) ∈ prog(T );
The minimality of B-trees is defined in the natural way.
Definition 4.5. (Minimal B-tree) We say a B-tree T is minimal, if {int(T )}=MM(prog(T )), i.e., int(T ) is the least model of prog(T ) (note that prog(T ) is non-disjunctive).
Example 4.5. (Cont'd)Note that {int(T )}=MM(prog(T )), and hence T is minimal. On the other hand, T ′ is not minimal because int(T ) ⊂ int(T ′ ) and int(T ) is a model of prog(T ′ ).
To characterize consistency of normal core programs P, we just have to properly define the set B of blocks.
Definition 4.6. A block for a normal core program P is any block (α, D, R), where α is a constant or a function from P , D is a set of predicates of P , and R is a rule set consisting of:
- All f-forward rules in P, for all functions f of P.
- In case α=c, the ruleA(x)← for each fact A(c)← inP. Otherwise, if α is a function f , all f -backward rules of P .
- (Reduct) For each local rule r ∈P such that B /∈D for all B(x)∈body-(r), the rule head(r)←body+(r).
By construction, for any B-tree T , where B is the set of all blocks for P , we have prog(T ) =P int(T ) . Hence, if T is minimal, then int(T )∈SM(P). On the other hand, for any I ∈ SM(P) we can build a minimal B-tree T with int(T )=I.
Theorem 4.1. If B is the set of all blocks for a normal core program P , then SM(P ) = {int(T ) | T is a minimal B-tree}. Therefore, P is consistent iff there exists a minimal B-tree.
4.2 Generating Minimal Trees
In this section we assume an arbitrary set B of blocks, and construct an automaton AB =〈Σ,Q, δ, q0, F〉, with Σ=B, which accepts exactly the minimal B-trees. To this end, let rules(B) and preds(B) denote the sets of all rules and predicate names occurring in B, respectively. Furthermore, let k be the number of function symbols occurring in B.
States Besides the initial state q0, the set of states Q contains the following:
- "test" states qc and qj for global testing of consistency and justification in a candidate tree;
- for each A ∈ preds(B), the states q∈A, q̸∈A and qjA for testing containment of predicates in a block and their justification;
- for each r ∈ rules(B), the states q∈ r and qc r for testing rule containment in a block and rule satisfaction;
- the states qp and qp 0 , . . . , qp k to ensure properness.
Transitions The transition function δ is defined as follows:
- (Initial state) For each σ∈Σ, there is a transition from q0:
Intuitively, from the initial state the automaton switches to states for testing consistency and minimality, and also for testing if the symbol at the root is indeed a root block and all the successors are proper child blocks, which is realized as follows.
- (Properness) For each σ = (α, D, R) in Σ and 1 ≤ i ≤ k, 2
Intuitively, the automaton fails if in the state qp 0 (resp., qp i ) it reads a block that is not a root block (resp., not a child block with function f s.t. i(f) = i). The marking state qp ensures recursively that the properness test is performed at each node of the tree.
- (Consistency) The test for consistency is defined in 3 steps. First, via the test state qc , the rules that need be satisfied
2 [E] stands for true, if E evaluates to true, and else for false.
are selected, and the state qc itself is propagated to the children. To this end, for every σ = (α,D,R) in Σ we have:
In the second step we move to satisfaction of the selected rules: for every σ ∈ Σ and r ∈ rules(B), we have
where ⃗Bn(x) = {B1(x), . . . ,Bn(x)}. Roughly, the rule r is satisfied, if either A is in the label of the node (resp., of some child or the parent), or some Bi (resp., B) is not.
Finally, the test for containment of labels is as follows: for each σ = (α, D, R) in Σ and each A ∈ preds(P ) we have:
- (Minimality testing) We use the test state qj to globally ensure justification of labels. For each σ=(α,D,R) in Σ:
Intuitively, when in state qj , the automaton simultaneously enters the states qjA in order to find justification for each predicate in D, and also propagates qj to all the children.
For the second step, let M(A) denote the set of all tuples 〈d, r, L〉, where d ∈ {-1, 0, 1, . . . , k}, r ∈ rules(B) has the predicate A in its head, and L ⊆ preds(B) such that:
- for local r, d = 0 and L = {B | B(x) ∈ body(r)};
- for f -forward r, d = -1 and L = {B | B(x) ∈ body(r)};
- for f -backward r, d= i(f ) and L={B | B(f (x))∈body(r)}.
Intuitively, we collect in M(A) the predicates and the direction that provide the justification. Now for each A ∈ preds(B) and each σ ∈ Σ, we have
Intuitively, the automaton guesses the rule that will be used to find the justification. Finally, we need the transition for the rule-containment state q∈ r : for each σ = (α,D,R) in Σ and rule r ∈ rules(B), we have δ(q∈ r , σ) = [r ∈ R].
Acceptance Condition We define the parity condition F : ∅⊆{qp , qc , qj }⊆Q. To understand this, observe that runs of AB can have 4 types of infinite paths: (i) paths where exactly one of qp , qc , qj occurs infinitely often, and (ii) paths where for some subset {A1, . . . ,An} ⊆ preds(B) only the justification states qjA1 , . . . , qjAn occur infinitely often. To ensure minimality, paths (ii) must be forbidden as they postpone justification indefinitely.
Theorem 4.2. Given a set B of blocks, AB accepts exactly the minimal B-trees, i.e., L(AB ) is the set of all minimal B-trees.
Note that the number of states in AB , where B is the set of all blocks of a normal core program P, is linear in |P|, and B is exponential in |P|. As testing non-emptiness of 2ATAs is feasible in time exponential in the number of states and polynomial in the size of the input alphabet [Vardi, 1998], by Theorem 4.2 and Proposition 3.1, we get the next completeness result; hardness can be shown by encoding an alternating Turing machine with polynomially bounded space.
Theorem 4.3. Testing consistency of normal core programs and of normal BD-programs under bounded predicate arities is EXPTIME-complete.
5 Consistency in Disjunctive BD-Programs
We analyze here the disjunctive case, and extend the method of the previous section to disjunctive core programs. To this end, we first characterize the minimal models of positive disjunctive ground programs in terms of split programs.
Definition 5.1. (Split) Let I be an interpretation for a positive (disjunctive) ground program P. A non-disjunctive positive program P ′ is called a split of P w.r.t. I if P ′ results from P by
- (a) replacing each rule r∈P such that |head(r)∩I|>1with a rule h←body(r), where h∈head(r) ∩ I is picked arbitrarily, and
- (b) replacing each rule r∈P such that |head(r)∩I|=∅with the constraint ←body(r).
By SP(P, I) we denote the set of all splits of P w.r.t. I.
Intuitively, a split P ′ is obtained from P in two steps. First, we identify the disjunctive rules having several of head atoms true in I, and delete all but one such atom. Then the rules with no head atoms true in I are transformed into constraints. We can then characterize the minimal models of disjunctive ground programs as follows.
Theorem 5.1. For any positive disjunctive ground program P it holds that I ∈ MM(P) iff I is the least model of every P ′ ∈ SP(P, I).
Proof. For the "only if" case, observe that if I ∈ MM(P), then I is also a model of every P ′ ∈SP(P, I), and that an arbitrary model of P ′ is also a model of P .
For the "if" case, suppose I is the least model of every P ′ ∈ SP(P, I) and I ̸∈MM(P). As already observed, I is a model of P. Hence, there must exist another model J ⊂I of P. Simply build a split P ′ of P w.r.t. I in two steps:
- replace each rule r∈P such that |head(r)∩I|>1 with a rule h←body(r), where
- (i) h∈head(r) ∩ I, if head(r) ∩J =∅, and
- (ii) h∈head(r) ∩ J, if head(r) ∩J ̸=∅;
- replace each rule r∈P such that |head(r) ∩ I|=∅ with the constraint ←body(r).
As easily seen, J is a model of P ′ , and thus I is not the least model of P ′ . Contradiction.
Due to the theorem above, minimal model checking for positive disjunctive programs reduces to minimal model checking over a set of non-disjunctive programs. Building on this, we show decidability of BD-programs using trees whose nodes are labeled with sets of blocks (or, hyperblocks) instead of a single block. Intuitively, each projection of such a tree, obtained by arbitrarily discarding all but one block in each node, provides us with a B-tree that encodes a different single split of a program. Consistency test for a program then amounts to finding a tree whose all projections are minimal B-trees.
We first formally define the notion of projection over a tree.
Definition 5.2. (Projection) Let Σ be an alphabet, and let Σ′ ⊆ 2Σ. A tree (T, L) over Σ is called a Σ-projection of a tree (T, L′ ) over Σ′ , if for every node n ∈ T , L(n) ∈ L′ (n).
Trees having block trees as projections are defined next.
Definition 5.3. (Minimal hyperblock trees) A hyperblock is any set of blocks (α, D, R) sharing the same α and D.
Let B be a set of blocks with k function symbols occurring in it, and H⊆2B be a set of hyperblocks. Then an H-tree is any H-labeled k-ary tree T = (T,L) satisfying the the following: (i) the blocks in L(ϵ) are root blocks, and (ii) for all x·c∈T , the blocks in L(x·c) are child blocks (α,D,R) with i(α)=c.
Note that B-projections of T are (proper) B-trees, and let int(T )=int(T ′ ) for an arbitrary B-projection T ′ of T (note that for any other projection T ′′ , int(T ′′ )=int(T ′ )).
We say T is minimal, if each B-projection of H is minimal.
To characterize stable models via hyperblock trees, we select suitable blocks and hyperblocks, taking into account splits.
Definition 5.4. A block for a (disjunctive) core program P is any block (α,D,R), where α is the constant c or a function of P, D is a set of predicates of P, and R is a rule set consisting of:
- All f-forward rules in P, for all functions f of P.
- In case α=c, the ruleA(x)← for each fact A(c)← inP. Otherwise, if α is a function f , all f -backward rules of P .
- (Reduct) Assuming X = {A(x) |A∈D}, for each local rule r∈P such that body-(r) ∩X=∅:
- a rule h←body+(r) for an arbitraryh∈head(r)∩X, in case head(r) ∩X ̸=∅, and
- the constraint←body+(r), in case head(r)∩X=∅.
A hyperblock for P is any ⊆-maximal set of blocks (α, D, R) for P sharing the same α and D.
The following characterization is now an easy consequence of Theorem 5.1 and the above Definitions 5.3 and 5.4.
Theorem 5.2. Let P be a core program, B the set of all blocks for P, and H ⊆ 2B the set of all hyperblocks for P. Then SM(P)={int(T ) | T is a minimal H-tree}.
Proof. (Sketch) Let T be a minimal H-tree and I =int(T ). Then I is the least model of prog(T ′ ) for each B-projection T ′ of T . Furthermore, due to the definition of hyperblocks for P , {prog(T ′ ) | T ′ is a B-projection of T } = SP(P I , I). Thus, I is the least model of every P ′ ∈SP(P I , I), and, by Theorem 5.1, a minimal model of P I and a stable model of P .
On the other hand, using Theorem 5.1, for any I ∈ SM(P ) we can easily build an H-tree T with int(T )=I.
To test existence of minimal H-trees, and hence consistency in core programs, we resort to the automaton of the previous section, and to a projection-based notion of acceptance.
Definition 5.5. (Hyperacceptance) Let A be a 2ATA with an alphabet Σ, and let Σ′ ⊆2Σ. We say a tree T over Σ′ is Σ′ - accepted by A, if A accepts each Σ-projection of T .
By combining Theorems 5.2 and 4.2, we get the following:
Proposition 5.3. Let P be a core program, B the set of all blocks for P, and H ⊆ 2B the set of all hyperblocks for P. Then SM(P)={int(T ) | T is H-accepted by AB }.
Thus, consistency of P amounts to the existence of an H-tree T such that AB accepts each B-projection of T . To decide the latter, we apply well-known automata conversions:
- We first transform AB into a 2ATA A1 that accepts the complement of L(AB ); this is well-known to be linear (the connectives in the transitions are inverted and the index of the sets in the parity condition increased by one).
- We transform A1 into an equivalent nondeterministic 1way tree automaton (1NTA) A2 using the translation in [Vardi, 1998]; this causes an exponential blow-up in the number of states. In contrast to 2ATAs, the automaton A2 moves only forward and its transitions are disjunctions of conjunctions.
- Building on A2, we define a 1NTA A3 that accepts exactly the trees T over H such that some B-projection T ′ of T is not accepted by AB . The components of A3 are the ones of A2 except the alphabet Σ3, which is Σ3 =H, and the transition relation δ3, which is δ3(q, σ) = ∨α∈σ δ2(q, α) for each state q ∈ Q3 and symbol σ ∈ Σ3. Intuitively, when scanning an H-labeled tree T , A3 simulates a run of A2 on some Bprojection T ′ of T , and accepts T iff A2 accepts some T ′ .
- By complementing A3, we obtain in linear time a 1ATA A4 that accepts a tree T over H iff T is H-accepted by AB .
The number of states and the alphabet H in the final automaton A4 are exponential in |P | (note that each set of predicate names from P together with a function or the constant c induces one hyperblock). Emptiness of a 1ATA is decidable in exponential time in the number of states and polynomial time in the size of the alphabet [Vardi, 1998]; overall, this yields double exponential time in |P|. By Proposition 5.3, we then obtain our main result on consistency testing; the hardness part can be proved by an encoding of an alternating Turing machine with exponentially bounded space.
Theorem 5.4. Testing consistency of disjunctive core programs and of disjunctive BD-programs under bounded predicate arities is 2EXPTIME-complete.
6 Further Results
Query entailment P |=μ ∃⃗x.A(⃗y) is efficiently reducible to (in)consistency testing in BD-programs, and thus has the same complexity. Briefly, if A(⃗y) is a y-atom and y is a variable, in cautious mode (μ=c), we can use a constraint ←A(⃗y),D(y), and in brave mode (μ=b) rules B(c)←not B(c), B(x)←B(f(x)), B(y)←A(⃗y),D(y), where D is an auxiliary domain predicate (cf. Example 3.3). The other cases can be easily reduced to this case. Note that, in fact, one can show 2EXPTIME-hardness of brave queries already over positive (disjunctive) core programs.
For BD-programs with unbounded predicate arities, we obtain an exponential increase in complexity (to completeness for 3EXPTIME, and 2EXPTIME in the non-disjunctive case). Intuitively, BD-programs are exponentially more succinct than core programs, and hence a reduction to a core program similar as in Proposition 3.1 is exponential in general.
However, the complexity of BD-programs is lower in case of a single function symbol (which still suffices to model a time line). Here, under bounded arities, consistency testing is EXPSPACE-complete in general, and PSPACE-complete in non-disjunctive case. Intuitively, the B-trees degenerate to words over B, and we can use word automata instead of tree automata, for which emptiness testing is accordingly easier.
7 Discussion and Conclusion
BD-programs enlarge the range of decidable ASP programs with function symbols, and constitute one of the few classes allowing for infinite stable models. Of the latter kind are finitary and finitely recursive programs [Bonatti, 2004], to which BD-programs are incomparable: they are neither finitary nor finitely recursive in general, but also do not capture any of the classes (as reasoning in them is semi-decidable in general).
Heymans [2006] used a similar automata construction as in Section 4 for conceptual logic programs, which have no function symbols and open answer set semantics. They also lack disjunction (in a usual sense) and are thus easier to handle.
Using our results, we can extend FDNC programs with inverses P - of binary predicates P, i.e., P -(f(x), x) equals P(x, f(x)). In this way, some Description Logics with inverse roles (e.g., ALCI) can be naturally captured and encoded efficiently into BD-programs. We just represent atoms P(x, f(x)) by Pf(x) and P -(f(x), x) by P - f (f(x)), and use BD-rules Pf (x)←P - f (f(x)) and P - f (f(x))←Pf(x).
Our results may shed also new light on DatalognS, which extends Datalog with n unary function symbols [Chomicki and Imielinski, 1993], and imply novel complexity results for this language. A detailed analysis remains for further work.
Other future work will also aim at more practical algorithms and applications (cf. Introduction and above).
@inproceedings{ijcai2009p132,
title = {Bidirectional Answer Set Programs with Function Symbols},
author = {Eiter, Thomas and Simkus, Mantas},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Craig Boutilier},
pages = {765--770},
year = {2009},
url = {https://ijcai.org/proceedings/2009/132},
}
TY - CPAPER TI - Bidirectional Answer Set Programs with Function Symbols AU - Eiter, Thomas AU - Simkus, Mantas T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 765 EP - 770 UR - https://ijcai.org/proceedings/2009/132 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: