Circumscription with homomorphisms: solving the equality and counterexample problems

ABSTRACT

One important facet of common-sense reasoning is the ability to draw default conclusions about the state of the world, so that one can, for example, assume that a given bird flies in the absence of information to the contrary. A deficiency in the circumscriptive approach to common-sense reasoning has been its difficulties in producing default that Tweety ≠ Blutto using ordinary circumscription, or conclude by default that a particular bird flies, if some birds are known not to fly. In this paper, we introduce a new form of circumscription, based on homomorphisms between models, that remedies these two problems and still retains the major desirable properties of traditional forms of circumscription.

REFERENCES

• 1: ~ARIEW, R. 1977. Did Ockham use his razor? Franclscatz Stud. 37, 5-17.
• 2: ~ARIMA, J. 1988. A connotative treatment of circumscription. Tech. Rep. TM-0640. Institute for ~New Generation Computer Technology (ICOT).
• 3: ~ARISTOTLE. De Caelo, vol. 2 of The Works of Aristotle Translated into Enghsh (translated by J. L. ~Stocks, 1922). Clarendon Press.
• 4: Genevieve Bossu , Pierre Siegel, Saturation, nonmonotonic reasoning and the closed-world assumption, Artificial Intelligence, v.25 n.1, p.13-63, Jan. 1985 [doi>10.1016/0004-3702(85)90040-2]
• 5: ~CHANG, C. C., AND KEISLER, H. J. 1990. Model Theory, 3rd ed. North Holland, Amsterdam, The ~Netherlands.
• 6: ~DAws, M. 1980. The mathematics of non-monotonic reasoning. Artzf. Itzt. 13, 73-8/).
• 7: Eliminating the fixed predicates from a circumscription, Artificial Intelligence, v.39 n.3, p.391-398, July 1989 [doi>10.1016/0004-3702(89)90018-0]
• 8: ~ENDERTON, H. B. 1972. A Mathematicalbztroductzon to Logic. Academic Press, Orlando, Fla.
• 9: David W. Etherington, Reasoning with Incomplete Information, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 10: David W. Etherington , Sarit Kraus , Donald Perlis, Nonmonotonicity and the scope of reasoning, Artificial Intelligence, v.52 n.3, p.221-261, Dec. 1991 [doi>10.1016/0004-3702(91)90068-U]
• 11: ~ETHERINGTON, D. W., MERCER, R. E., AND REITER, R. 1985. On the adequacy of predicate ~circumscription for closed-world reasoning. Computat. Int. 1, 11-15.
• 12: ~GOGUEN, J. A., AND BURSTALL, R. M. 1985. Institutions: Abstract model theory for computer ~science. Tech. Rep. CSLI-85-30. Center for the Study of Language and Information. Stanford ~Umv., Stanford, Calif.
• 13: ~GROSOF, B. N. 1991. Generalizing prioritJzation. In Proceedings of the 2nd b~ternattonal Confer- ~ence on Prtnctples of Knowledge Representation and Reasolting. Morgan-Kaufmann, San Mateo, ~Calif., pp. 289-300.
• 14: ~HALMOS, P. R. 1970. Naive Set Theol. Springer-Verlag, New York.
• 15: ~LIFSCH1TZ, V. 1984. Some results on circumscription. Tech. Rep. STAN-CS-84-1019. Stanford ~Univ., Stanford, Calif.
• 16: ~LIFS~'HITZ, V. 1985. Computing circumscription. In Proceedings oflJCAI-85. Morgan-Kaufmann, ~San Mateo, Calif., pp. 121-127.
• 17: V. Lifschitz, Pointwise circumscription, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 18: ~LIFSCmTZ, V. 1990. Circumscription. In Handbook of Logic in AI and Logic' Programming. ~Oxford University Press.
• 19: ~MCCARTHY, J. 1977. Epistemological problems of artificial intelligence. In Proceedtngs of ~1JCAI-77. pp. 1038-1044.
• 20: J. McCarthy, Circumscription—a form of non-monotonic reasoning, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 21: J. McCarthy, Applications of circumscription to formalizing common-sense knowledge, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 22: ~MCCARTHY, J. 1988. Keeping things simple--Ockham's razor for computer programs. High ~Noon, easy listening lecture, Stanford Univ., Stanford, Calif., Friday, April 15, 1988.
• 23: 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]
• 24: ~MO1NARD, Y., AND ROLLAND, R. 1991. Circumscription and definability. In Proceedings of ~HC241-91. Morgan-Kaufmann, San Mateo, Calif., pp. 432-437.
• 25: ~PERLIS, D. 1986. On the consistency of commonsense reasoning. Computat. h~t. 2, 180-190.
• 26: D Perlis, Circumscribing with sets, Artificial Intelligence, v.31 n.2, p.201-211, Feb. 1987 [doi>10.1016/0004-3702(87)90020-8]
• 27: ~RklTER, R. 1980.A logic for default reasoning. Artif. bit. 13, 1, 2; 81-132.
• 28: Y. Shoham, A semantical approach to nonmonotonic logics, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987

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:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General
          Subjects: Philosophical foundations
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic

General Terms:
Theory

Keywords:
circumscription, common sense reasoning