Compiling Prioritized Circumscription into Extended Logic Programs
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 182-188.
© 1997 International Joint Conferences on Artificial Intelligence
Abstract
We propose a method of compiling circumscription into Extended Logic Programs which is widely applicable to a class of parallel circumscription as well as a class of prioritized circumscription. In this paper, we show theoretically that any circumscription whose theory contains both the domain closure axiom and the uniqueness of names axioms can always be compiled into an extended logic program II, so that, whether a ground literal is provable from circumscription or not, can always be evaluated by deciding whether the literal is true in all answer sets ofii, which can be computed by running II under the existing logic programming interpreter.
- [de Kleer and Konolige, 1989] de Kleer, J. and Kono- lige, K. Eliminating the Fixed Predicates from a Cir- cumscription. Artificial Intelligence 39, pages 391- 398, 1989.
- [Etherington, 1987] David W. Etherington. Relating Default Logic and Circumscription. Proc. IJCAI-87, pages 489-494, 1987. IJCAI
- [Gelfond and Lifschitz, 1988a] Gelfond, M. and Lifs- chitz, V. Compiling Circumscriptive Theories into Logic Programs. Proc . AAAJ-88, pages 455-459. Ex- tended version in: Proc. 2nd Int. Worksh op on Non- monotonic Reasoning, LNAI 346, pages 74-99, 1988.
- [Gelfond and Lifschitz, 1988b] Gelfond, M. and Lifs- chitz, V. The Stable Model Semantics for Logic Pro- gramming. Proc . LP '88, pages 1070-1080, 1988.
- [Gelfond and Lifschitz, 1991] Gelfond, M. and Lifschitz, V. Classical Negation in Logic Programs and Dis- junctive Databases. N ew Generation Computing 9, pages 365-385, 1991.
- [Ginsberg, 1989] Matthew L. Ginsb erg, A Circumscrip- tive Theorem Prover, Artificial Int elligence 39, pages 209-230, 1989. .
- [Inoue, 1992] Inoue, K. Linear Resolution for Conse- quence Finding, Artificial Intellig en ce 56, pages 301- 353, 1992.
- [Inoue and Sakama, 1994] Inoue, K. and Sakama, C. On Positive Occurrences of Negation as Failure. Proc. KR '94, pages 293-304, 1994.
- [Lifschitz, 1985] Lifschitz, V. Computing Circumscrip- tion. Proc. IJCAI-85, pages 121-127, 1985.
- [McCarthy, 1980] McCarthy, J. Circumscription -a Form of Non-monotonic Reasoning. Artificial Intelli- gence 13, pages 27-39, 1980.
- [Przymusinski, 1987] Przymusinski, T. On the Declar- ative Semantics of Deductive Databases and Logic Programs. in Foundations of Deductive Databases and Logic Programming ( J. Minker, Ed.) , Morgan Kaufmann, pages 193-216, 1987.
- [Reiter, 1980] Reiter, R. A Logic for default reasoning. Artificial Intellig ence 13, pages 81-132, 1980.
- [Sakama and Inoue, 1995] Sakama, C. and Inoue, K. Embedding Circumscriptive Theories in General Dis- junctive Programs. Proc. 3rd International Confer- ence on Logic Programming and Nonmonotonic R ea- soning, 1995, LNAI 928, pages 344-357, Springer.
- [Sakama and Inoue, 1996] Sakama, C. and Inoue, K. Representing Priorities in Logic Programs. Proc. Joint International Conference and Symposium on Logic Programming, pages 82-96, 1996.
- [Satoh and lwayama, 1992] Satoh, K. and lwayama, N. A Query Evaluation Method for Abductive Logic Programming. Proc. Joint Int ernational Conference and Symposium on Logic Programming, pages 671- 685, 1992.
- [Wakaki and Satoh, 1995] Wakaki, T and Satoh, K. Computing Prioritized Circumscription by Logic Programming. Proc. 12th International Conference on Logic Programming, pages 283-297, 1995.
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
Circumscription [McCarthy, 1980; Lifschitz, 1985] was proposed to formalize the commonsense reasoning under incomplete information.
So far, many studies have been proposed to explore the approach of the use of logic programming for the automation of circumscription based on the relationship between the semantics of circumscription and the seman tics of logic programs.
Gelfond and Lifschitz [1988a] was the first to consider a computational method for some restricted class of pri oritized circumscription which compiles circumscriptive theories into a stratified logic program. Though their method is computationally efficient, the applicable class is too limited.
So we proposed the extension of Gelfond and Lifs chitz's method which also compile prioritized circum scription into a stratified logic program [Wakaki and Satoh, 1995]. With keeping the efficiency of Gelfond and Lifschitz's method, our method expands the appli cable class of circumscription by making use of the re sult [Lifschitz, 1985] about parallel circumscription of a solitary formula. However, as far as a class of stratified logic programs is considered as the target language to which circumscription .is compiled, the applicable class is limited within a class of circumscription which has a
Ken Satoh
Division of Electronics and Information Engineering
Hokkaido University
N13W8, Kita-ku, Sapporo 060, Japan
unique minimal model since every stratified logic pro gram has a unique perfect model [Przymusinski, 1987]. But there are many examples of nonmonotonic reason ing whose intended meaning cannot be represented by a unique model such as multiple extension problem, a class of circumscription which has fixed predicates, and so on.
Recently Sakama and Inoue [1995; 1996] proposed two methods both of which compile circumscription into classes of more general logic programs whose semantics are given by stable models for the first one [Sakama and Inoue, 1995] and by preferred answer sets for the second one [Sakama and Inoue, 1996]. Though both of their methods can handle the multiple extension problem as well as circumscription with fixed predicates, the first one is only applicable to parallel circumscription but not to prioritized circumscription. On the other hand, the second one is applicable to prioritized circumscrip tion, but it gives only the semantic aspects and is lack of the feasible logic programming interpreter for prioritized logic programs proposed by them as the target language into which prioritized circumscription is compiled.
In this paper, we propose a new method of compiling circumscription into extended logic programs proposed by Gelfond and Lifschitz [1991] as its target language. It is widely applicable to a class of parallel circumscription as well as a class of prioritized circumscription. Show ing the semantic correspondence between circumscrip tion with fixed predicates and Reiter's default theory which generalizes Theorem 2 in [Etherington, 1987], we can give not only the semantic relationship between a class of parallel circumscription and a class of extended logic programs but also the one between a class of prior itized circumscription and a class of extended logic pro grams. As a result, any circumscription whose theory contains both the domain closure axiom and the unique ness of names axioms can always be compiled into an extended logic program II, so that, whether a ground lit eral is provable from circumscription, can always be eval uated by deciding whether the literal is true in all answer sets of II. This can be computed by running II under the existing logic programming interpreter such as Satoh and Iwayama's top-down query evaluation procedure for ab ductive logic programming [Satoh and Iwayama, 1992].
Finally, we present that our approach exploiting clas sical negation .., can also give an extension of Sakama and Inoue's first method [1995) to make it possible to compute prioritized circumscription.
The structure of the paper is as follows. In section 2, we give preliminaries related to circumscription and extended logic programs. In section 3, we provide two syntactical definitions of extended logic programs into which parallel circumscription and prioritized circum scription are compiled respectively. Then, we present theorems and corollaries on which our method is theo retically based, along with examples. We finish section 4 with comparing our method with related researches.
2 Preliminaries
We review parallel circumscription and prioritized cir cumscription as well as the synta..x and semantics of extended logic programs (ELP) [Gelfond and Lifschitz, 1991) in a slightly extended form.
Let T(P, Z) be a sentence, P be a tuple of minimized predicates and Z be a tuple of variable predicates. Q de notes the rest of the predicates occurring in T , called the fixed predicates. Then parallel circumscription of P in T(P, Z) with variable Z is denoted by Circum(T; P; Z). If P is broken into parts P 1 , ··· , pk, then the circum scription assigning a higher priority to the members of pi than to the members of pi for i < j is denoted by the following prioritized circumscription:
Prioritized circumscription can be represented by using parallel circumscription as follows:
Extended logic programs have the expressive power to represent classical negation (..,) along with negation as failure (not) which enables us to represent incomplete information.
A extended logic program is a set of rules of the form:
where n ~ m ~ 0, and L and Li 's are literals. Each rule of the form (2.3) is called an integrity constraint.
The semantics of an extended logic program is an ex tension of the stable model semantics[Gelfond and Lif schitz, 1988b) and is given by the answer sets [Gelfond and Lifschitz, 1991]. The answer sets of an extended logic program are defined in the following two steps.
- Let TI be a set of ground rules of an extended logic program not containing not and Lit be the set of ground literals in the language. The answer set, a(TI), of TI is the smallest subset S of Lit satisfying the conditions:
- (a) For any rule L +- L1, ... , Lm in 11, if L1, ... ,Lm E S, then L E S;
- (b) For any integrity constraint +- L1, . .. , Lm m 11, if L1. ... , Lm E S, then S =Lit;
- (c) if S contains a pair of complementary literals, then S =Lit.
- Let 11 be any extended logic program without vari ables. For any set S ~ Lit, let 11 be the set of rules without not obtained from n by deleting
- (a) every rule containing a formula notL in its body with L E S, and
- (b) every formula notL in the bodies of the remain ing rules.
Then, S is an answer set of 11 if S is the answer set of ITS, that is, S = a(ITs).
Let E be a set of clauses. Then Th(E) stands for a set of clauses which are theorems of E. A clause in Th(E) which is not properly subsumed by any theorem in Th(E) is called a characteristic clause. j.tTh(E) de notes the set of all characteristic clauses in Th(E) [Inoue, 1992).
3 Translation from Circumscription into Extended Logic Programs
We give a translation from circumscription to extended logic programs. Parallel circumscription is translated into ELP na and prioritized circumscription is trans lated into ELP rr.a respectively.
In the following Definition 3.1 and Definition 3.2, we restrict a first order theory T to the one which is function-free and contains both the domain closure axiom (DCA) and uniqueness of names axioms (UNA). We consider T as a set of clauses:
We suppose that every clause in E containing variables is replaced by all its ground instances obtained by sub stituting every ground term in DCA for each variable. t stands for a tuple of ground terms occurring in DCA.
Definition 3.1
Given parallel circumscription Circum(VT; P; Z) where Vis a universal closure, ELP rra is constructed as follows:
- For any minimized predicate p from P and any t,
- For any fixed predicate q from Q and any t,
- For any clause C d;j f 1 V f2 V ... V fn in j.tTh(E) and any contrapositive of C such as -,f; 2 /\ ·· · I\ -,fin :J f; 1 and -,fi 1 1\ -,f; 2 1\ ... 1\ -,fin :J false,
where l;i E {fl,···,fn} (for j = 1, ... ,n). As a special case, if C is a unit literal f ,
Definition 3.2
Given prioritized circumscription as follows:
where pr(l:::; r:::; k ),Z,Q are tuples of predicate symbols such as [(Prh, ... , (Pr)e.],[Zl, ... , Zm],[QI. ... , Qn], ELP IIi3 is constructed in the following two steps:
- According to (2.1), a given prioritized circumscrip tion is represented by the conjunction of k parallel circumscriptions. So, let every ith (1 :::; i :::; k) par allel circumscription,
be transformed in such a way that all predicate symbols occurring in it are renamed b~ using Pil, ... ,Pik, Zi,Qi instead of P\ ... ,P, Z,Q, which leads to as follows:
where Ti denotes T(Pi 1 , ··· , Pik, Zi, Qi), and Pir, Zi, Qi are tuples of predicate sym bols such as [(Pir)I, ... , (Pir)tr],[(Zi)I, ... , (Zi)m], [( Qi)I, · · ·, ( Qi)n]·
- ELP IIi3 consists of all rules from (II"'h, ... , (II"')k and II 1 where
- (a) each (II"'); is an extended logic program (ELP) which is constructed from the ith renamed par allel circumscription (3.1) according to Defini tion 3.1.
- (b) II 1 is an extended logic program which consists of the following rules:
For any predicate u from P, Z, Q and any t,
where u and u; stand for any predicate symbol of (Pr)J, Z 9 , Qh and any one of (Pir)1, (Zi) 9 , (Qi)h respectively.
First of all, we show the following theorem which gener alizes Theorem 2 in [Etherington, 1987].
Theorem 3.3 Assume that T is a first order theory in cluding DCA and UNA. Then, those formulas true in every default extension of the default theory:
are precisely those theorems of Circum(T; P; Z) where P,Q and Z are tuples of minimized, fixed and variable predicate symbols respectively.
Proof:(sketch) According to Theorem 1 in [de Kleer and Konolige, 1989], circumscription including fixed predicates q; can be logically equivalently transformed into circumscription without fixed predicates where q; and ·q; are added to circumscribed predicates. As a result, this theorem is proved by applying Etherington's result [Etherington, 1987] about correspondence between circumscription without fixed predicates and Reiter's de fault theory [Reiter, 1980] to the transformed circum scription.
Based on Theorem 3.3 as well as a 1-1 correspondence between the extensions of a default theory and the an swer sets of an extended logic program shown in [Gel fond and Lifschitz, 1991], the semantic relationships be tween circumscription and the translated ELPs II"' ,IIi3 are given as follows.
Theorem 3.4 For any ground literal G of the language ofT whose predicate symbol is not equality, it holds that,
iff G is true in all answer sets of ELP II"',
where ELP II"' is constructed from Circum(VT; P; Z) by using definition 3.1.
Theorem 3.5 For any ground literal G of the language ofT whose predicate symbol is not equality, it holds that,
iff G is true in all answer sets of ELP ITi3 . where ELP ITi3 is constructed from
by using Definition 3.2.
Remarks. Theorem 3.4 and Theorem 3.5 can be eas ily generalized for a ground formula F instead of for a ground literal G.
Satoh and Iwayama [1992] show that whether a ground atom G is true in all stable models of a normal logic pro gram IT, can be decided by running their top-down query evaluation procedure for abductive logic programs where an abductive framework is given by (IT, A} in which A is a set of predicate symbols called abducible predicates. Their result is given as follows:
Suppose that a normal logic program IT is consistent , which means that there exists a stable model of IT, and all ground rules obtained by replacing all variables in each rule in IT by every element of its Her brand universe are finite. Then it holds that,
under the abductive framework (IT,{}).
where derive is a procedure given by them and not in its first argument denotes the negation-as-failure operator.
Since all ground rules in ELP IT"' and ITi3 constructed by using Definition 3.1 and Definition 3.2 respectively are finite, we can make use of their result in a slightly extended form, and Theorem 3.4 and Theorem 3.5 can be said in other words by the following corollaries.
Corollary 3.6 Suppose that T is consistent and function-free. For any ground literal G of the language ofT whose predicate symbol is not equality, it holds that,
iff derive( not G, {}) fails
under the abductive framework (II"',{}),
where ELP II"' is constructed from Circum(Vr; P; Z) by using Definition 3.1.
Corollary 3. 7 Suppose that T is consistent and function-free. For any ground literal G of the language ofT whose predicate symbol is not equality, it holds that,
under the abductive framework (II, {}).
where II consists of all rules ofELP IJ.B in Definition .':1.2 plus rules, +- u(t), -,u(t), for every predicate u in T.
Remarks. There is Ginsberg's early work [Ginsberg, 1989] on evaluating circumscription using abduction. But his method does not exploit the logic programming.
Example 3.8
Our compilation can handle circumscription representing multiple inheritance. Consider parallel circumscription:
where T d;j l::U DCA U UN A, 1:: consists of the following clauses and DCA is x=Nixon:
A set Q of fixed predicates is {republican, quaker} in this example. Hereafter we abbreviate pacifist, republican, quaker and Nixon to pac, rep,quak and N respectively.
After replacing a variable x in every clause in 1:: by a ground term N in DCA, pTh('E) is obtained as follows:
According to Definition 3.1, let us construct ELP II"' from circumscription (1).
- For minimized predicates ab1, ab2 and a constant N,
- For fixed predicates rep, quak and a constant N,
- For all contrapositives of all clauses of pTh(l::) ,
As a result, II"' has two answer sets:
Example 3.9 Let us compile the following prioritized circumscription:
Since 1:: = {p V q, q V r }, it holds that 1:: = pTh(l::). Contrapositives of p V q are as follows:
and those of q V r are as follows:
According to (2.1), it holds that
Then according to Definition 3.2, predicate symbols oc curring each parallel circumscription are renamed as fol lows:
Therefore ELPs (II"')t, (II"'h constructed from (2) and (3) respectively as well as II, are obtained as follows:
ELP IIi3 has the only one answer set:
where IIi3 d;j (IIah U (IIa)2 U II-y.
Thus according to Theorem 3.5, we can conclude that
but neither r nor ..,r is provable from this prioritized circumscription.
In the following, we give an extension of Sakama and Inoue's first method [1995]. According to their method, parallel circumscription is translated into a general disjunctive program (GDP) whose semantics is given by stable models. Alternatively, they also show the translation of parallel circumscription into an Extended disjunctive program (EDP) whose semantics is given by the answer sets, which just corresponds to the stable models of the translated GDP. Each of their methods is applicable to a class of parallel circumscription, but not to prioritized circumscription. Our target language EL~ has the expressive power of classical negation ..,, wh1ch enables us to compute prioritized circumscription as is shown in Theorem 3.5. Since the classical nega tion is also available to EDP, we can make use of our method to extend their alternative method whose target language is EDP, so that it may become applicable to a class of prioritized circumscription as follows.
Definition 3.10 [Sakama and Inoue, 1995]
Given parallel circumscription Circum(VT; P; Z) , EDP rra is constructed as follows , where DCA and UNA are incorporated in a first order theory T since only its Her brand models are considered, and p1 , ... , pe, z1, ... , zm, and q1, ... , qn are used to denote atoms from P Z and Q respectively. '
- For any clause in T of the form:
rra has the rule:
- For every clause in ~tTh(E) of the form:
rra has the rule:
- For any atom p, z, q, rra has the rule:
Remarks. It is shown in [Sakama and Inoue, 1995] that there is a 1-1 correspondence between the models of parallel circumscription and the answer sets of the translated EDP rra.
Definition 3.11
Given prioritized circumscription:
EDP IIi3 is constructed in the following two steps:
- This is the same as the first step given by Defini tion 3.2.
- EDP IIi3 consists of all rules from (IIah , ... , (IIa)k and II-y where
- (a) each (IIa); is an extended disjunctive program (EDP) which is constructed from the ith re named parallel circumscription (3.1) according to Definition 3.10.
- (b) Il-y is the same set given by Definition 3.2.
~hen the relationship between prioritized circumscrip tion and the translated EDP IIi3 are given as follows.
Theorem 3.12 Let F be a ground formula of the lan guage of T and equality does not occur as a predicate symbol in F . Then, it holds that, for any F,
where EDP IIi3 is constructed from
by using Definition 3.11.
Example 3.13
Consider prioritized circumscription given in Exam ple 3.9. We apply Theorem 3.12 instead of Theorem 3.5 to it. Then according to Definition 3.11, the translated EDPs (IIah and (IIa)2 are as follows:
Since P = {p1}, Z = {q1,r1}, Q = c/J in the renamed circumscription: Circum({p1 V q1, q1 V r1};p1; q1, rl) ,
Since P = {q2}, Z = {r2}, Q = {p2} in the renamed circumscription: Circum( {p2 V q2, q2 V r2}; q2; r2),
II'Y is obtained as the same one shown in Example 3.9. As a result, EDP II.B has the following two answer sets:
where II.B consists of all rules in the above (II")I, (II")2 and II 'Y. Both ..,p and q are true in all of these answer sets, but so is neither r nor -,r. Notice that this is the same evaluation result as the one in Example 3.9.
4 Related Works and Conclusion
In this paper, we present a method of compiling circum scription into extended logic programs which is widely applicable to parallel circumscription as well as priori tized circumscription. Our method always enables us to compute any circumscription whose theory includes both DCA and UNA by compiling it into ELP II, which can be evaluated by using the existing logic programming in terpreter such as Satoh and lwayama's top-down query evaluation procedure for abductive logic programming.
In the following, we compare our method with related researches from the viewpoints of the applicable class as well as the computational efficiency and feasibility.
- Gelfond and Lifschitz's method [1988a] as well as our previous method [Wakaki and Satoh, 1995] are the most efficient since they are as efficient as the evaluation of a stratified logic program. But their applicable classes are limited within a class of cir cumscription which has a unique model as men tioned in the introduction of this paper.
- In Sakama and Inoue's first method [1995] , paral lel circumscription is translated into a general dis junctive program (GDP). This method is applica ble to a wide class of parallel circumscription, but inapplicable to prioritized circumscription though a class of GDP has the expressive power of the positive occurrences of negation as failure [Inoue and Sakama, 1994]. The most important difference between their GDP and our ELP i~ whether classical negation .., is available or not. Theorem 3.12 shows that our approach exploiting classical negation can also give an extension of their alternative method whose target language is EDP, so that it may be come applicable to prioritized circumscription.
- In Sakama and Inoue's second method [1996], par allel circumscription as well as prioritized circum scription is translated into prioritized logic pro grams proposed by them whose declarative meaning is given by preferred answer sets defined by them. Their method, however , is immature for the purpose of the automation of circumscription since their pri oritized logic program is not feasible because their method gives only the semantic aspects, but proce dural issues for the query evaluation are left as their future works.
Our future work is to implement our method proposed in this paper. ·
@inproceedings{ijcai1997p28,
title = {Compiling Prioritized Circumscription into Extended Logic Programs},
author = {Wakaki, Toshiko and Satoh, Ken},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {182--188},
year = {1997},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1997/28},
}
TY - CPAPER TI - Compiling Prioritized Circumscription into Extended Logic Programs AU - Wakaki, Toshiko AU - Satoh, Ken T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 182 EP - 188 UR - https://ijcai.org/proceedings/1997/28 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: