Completeness Results for Circumscription

Donald Perlis and Jack Minker

Computer Science Department
University of Maryland
College Park

The complete paper is available in:

• PostScript

Abstract

We investigate the model theory of the notion of circumscription, and find completeness theorems that provide a partial converse to a result of McCarthy. We show that the circumscriptive theorems are precisely the truths of the minimal models, in the case of various classes of theories, and for various versions of circumscription. We also present an example of commonsense reasoning in which first-order circumscription does not achieve the intuitive and desired minimization.

Bibliography

• Clark, K. [1978] "Negation as Failure", In: Logic and Databases, Gallaire, H. and Minker, J., Eds.) Plenum Press, NY 1978, 293-322.
• van Dalen, D. [1983] Logic and Structure. 2nd edition. Springer-Verlag. Davis, M. [1980] "The Mathematics of NonMonotonic Reasoning". Artificial Intelligence 13 (1980), 73-80.
• Doyle, J. [1984] "Circumscription and Implicit Definability", Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19, 1984.
• Etherington, D. personal communication, Week on Logic and Artificial Intelligence, Univ. of Maryland, Oct. 22- 26, 1984.
• Etherington, D., Mercer, R., and Reiter, R. [1984] "Drawing the Line Around Circumscription", Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19, 1984.
• Kueker, D. "Another Failure of Completeness for Circumscription", photocopied notes, Week on Logic and Artif- icial Intelligence, Univ. of Maryland, Oct. 22-26, 1984.
• Lifschitz, V. "Some Results on Circumscription", Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19,
• 1984. McCarthy, J. [1980] "Circumscription--A Form of Non-Monotonic Reasoning". Artificial Intelligence 13 (1980), 27-39.
• McCarthy, J. [1984a] "Applications of Circumscription to Formalizing Common Sense Knowledge" Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19, 1984.
• McCarthy, J. [1984b] personal communication, Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19, 1984.
• Minker, J. and Perlis, D. [1984] "Protected Circumscription". Preprint, Workshop on Nonmonotonic Reasoning, Mohonk, Oct. 17-19, 1984.
• Reiter, R. [1978] "On Closed World Databases". In: Logic and Data Bases, (Gallaire, H. and Minker, J., eds.) Plenum, 1978, 55-76.
• Reiter, R. [1980] "Equality and Domain Closure in First-Order Databases". JACM 27, 2 (April 1980), 235-249.
• Reiter, R. [1982] "Circumscription Implies Predicate Completion (Sometimes)". Proceedings of AAAI-82, 418-420.