Autoepistemic logic

ABSTRACT

Autoepistemic logic is one of the principal modes of nonmonotonic reasoning. It unifies several other modes of nonmonotonic reasoning and has important application in logic programming. In the paper, a theory of autoepistemic logic is developed. This paper starts with a brief survey of some of the previously known results. Then, the nature of nonmonotonicity is studied by investigating how membership of autoepistemic statements in autoepistemic theories depends on the underlying objective theory. A notion similar to set-theoretic forcing is introduced. Expansions of autoepistemic theories are also investigated. Expansions serve as sets of consequences of an autoepistemic theory and they can also be used to define semantics for logic programs with negation. Theories that have expansions are characterized, and a normal form that allows the description of all expansions of a theory is introduced. Our results imply algorithms to determine whether a theory has a unique expansion. Sufficient conditions (stratification) that imply existence of a unique expansion are discussed. The definition of stratified theories is extended and (under some additional assumptions) efficient algorithms for testing whether a theory is stratified are proposed. The theorem characterizing expansions is applied to two classes of theories, K1-theories and ae-programs. In each case, simple hypergraph characterization of expansions of theories from each of these classes is given. Finally, connections with stable model semantics for logic programs with negation is discussed. In particular, it is proven that the problem of existence of stable models is NP-complete. —Authors' Abstract

REFERENCES

• 1: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: CHELLAS, B.F. Modal Logic. Cambridge University Press, Cambridge. Mass., 1980.
• 4: COHEN, P. J.Set Theory and the Continuum Hypothesis. W. A. Bemjamin. Reading, Mass., 1966.
• 5: GAREY, M. R., AND JOHNSON, D. S.Computers and Intractability. Freeman, San Francisco, Calif., 1979.
• 6: GELFOND, M.On stratified autoepistemic theories In Proceedings of AAAI-87. 1987, pp. 207-211.
• 7: GELFOND, M., AND LIFSCHITZ, V.The stable model semantics for logic programming. In R. Kowalski, and K. Bowen, eds., Logic Programming: Proceedings of the 5th international Conference and Symposium, 1988, pp. 1070-1080.
• 8: Matthew L. Ginsberg, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 9: HALPERN, J. Y., AND MOSES, Y.Towards a theory of knowledge: Preliminary report. In R. Reiter, ed., Proceedings of Workshop on Non-Monotonic Reasoning. AAAI, Mohonk, N.Y., 1984, pp. 125-143.
• 10: IMIELINSKI, T.Faithfulness in knowledge bases. Unpublished manuscript.
• 11: Kurt Konolige, On the relation between default and autoepistemic logic, Artificial Intelligence, v.35 n.3, p.343-382, July 1988 [doi>10.1016/0004-3702(88)90021-5]
• 12: LIFSCHITZ, V.Circumscriptive theories: A logic-based framework for knowledge representation. J. Philos. Logic 17 (1988), 391-441.
• 13: MAREK, W.Stable theories in autoepistemic logic. Fund. Inf. XII (1989), 243-254.
• 14: MCCARTHY, J.Circumscription -- A form of non-monotonic reasoning. Artif. Int. 13 (1980), 27-39.
• 15: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• 16: MOORE, R. C.Possible-world semantics autoepistemic logic. In R. Reiter, ed., Proceedings of Workshop on Non-Monotonic Reasoning. AAAI, Mohonk, N.Y., 1984, pp. 344-354.
• 17: Robert C. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence, v.25 n.1, p.75-94, Jan. 1985 [doi>10.1016/0004-3702(85)90042-6]
• 18: MOORE, R. C. Autoepistemic logic. In P. Smets, E. H. Mamdani, D. Dubois, and H. Prade, eds., Non-Standard Logics for Automated Reasoning. Academic Press, Orlando, Fla., 1988, pp. 105-127.
• 19: Ilkka Niemelä, Decision Procedure for Autoepistemic Logic, Proceedings of the 9th International Conference on Automated Deduction, p.675-684, May 23-26, 1988
• 20: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 21: REITER, R. On closed world databases. In H. Gallaire, and J. Minker, eds., Logic and Data Bases. Plenum Press, New York, N.Y., 1978, pp. 55-76.
• 22: REITER, R.A logic for defaults reasoning. Artif. lnt. 13 (1980), 81-132.
• 23: J. C. Shepherdson, Negation in logic programming, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: STALNAKER, R.A note on non-monotonic modal logic. Unpublished manuscript.
• 25: A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming; Mechanical theorem proving

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Theory