Abstract
Circumscription has been proposed by researchers in artificial intelligence as a means of formalizing common-sense conclusions about the state of the world, by assuming that unlikely or abnormal states do not occur unless there is evidence to the contrary. Circumscription produces this effect by placing a partial order on the models of a theory, and accepting as true those statements that are true in all models of the theory that are minimal with respect to the partial order. This allows one to conclude, for example, that a car will start when the key is turned in its ignition, and that the neighbors' unseen dog has four legs and a tail. Here we describe a different use for circumscription, that of specification of semantics for updating knowledge bases expressed in first-order logic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.R. Apt, H. Blair and A. Walker, Towards a theory of declarative knowledge, in:Foundations of Deductive Databases and Logic Programming, J. Minker (ed.) (Morgan Kaufmann, 1987).
M. Dalal, Investigations into a theory of knowledge base revision: Preliminary report,AAAI-88, Minneapolis (August 1988).
J. de Kleer, An assumption-based truth maintenance system, Art. Int. 28 (1986).
J. Doyle, A truth maintenance system, Art. Int. 12 (1979).
D.W. Etherington,Reasoning With Incomplete Information (Morgan Kaufmann, Los Altos, 1988).
R. Fagin, J.D. Ullman and M.Y. Vardi, On the semantics of updates in databases,Proc. 2nd ACM Symp. on Principles of Database Systems (April 1983).
R. Fagin, G.M. Kuper, J.D. Ullman and M.Y. Vardi, Updating logical databases, Adv. Comput. Res. 3 (1986).
K.D. Forbus, Introducing actions into qualitative simulation,Proc. Int. Joint Conf. on Artificial Intelligence, Detroit (August 1989).
P. Gärdenfors and D. Makinson, Revisions of knowledge systems using epistemic entrenchment,Proc. Conf. on Theoretical Aspects of Reasoning About Knowledge, Asilomar (March 1988).
P. Gärdenfors,Knowledge in Flux: Modeling the Dynamics of Epistemic States (Bradford Books, MIT Press, 1988).
M.L. Ginsberg, Counterfactuals, Art. Int. 30 (1986).
M.L. Ginsberg and D.E. Smith, Reasoning about action I: A possible worlds approach, in:Readings in Nonmonotonic Reasoning, M.L. Ginsberg (ed.) (Morgan Kaufmann, Los Altos, 1987).
S. Hegner, Specification and implementation of programs for updating incomplete information databases,Proc. 6th ACM Symp. on Principles of Database Systems, San Diego (March 1987).
H. Katsuno and A.O. Mendelzon, A unified view of propositional knowledge base updates,Proc. Int. Joint Conf. on Artificial Intelligence, Detroit (August 1989). An expanded version appears as Propositional knowledge base revision and minimal change, Technical Report KRR-TR-90-3, University of Toronto (March 1990).
V. Lifschitz, Computing circumscription,Proc. Int. Joint Conf. on Artificial Intelligence, Los Angeles (1985).
V. Lifschitz, On the satisfiability of circumscription, Art. Int. 28 (1986).
On the declarative semantics of logic programs with negation, in:Foundations of Deductive Databases and Logic Programming, J. Minker (ed.) (Morgan Kaufmann, 1987).
V. Lifschitz, Pointwise circumscription, in:Readings in Nonmonotonic Reasoning, M.L. Ginsberg (ed.) (Morgan Kaufmann, Los Altos, 1987).
J. McCarthy, Circumscription — A form of non-monotonic reasoning, Art. Int. 13 (1980).
J. McCarthy, Applications of circumscription to formalizing common-sense knowledge, Art. Int. 28 (1986).
K. Myers and D.E. Smith, On the persistence of derived information,National Conf. on Artificial Intelligence, Minneapolis (August 1988).
G. Oddie, Verisimilitude, fromThe Logic and Philosophy of Scientific Change, in: Acta Philosophica Fennica 30 (2–4) (1978).
N. Pollack,Subjunctive Reasoning (Reidel, Dordrecht, 1976).
A.S. Rao and N.Y. Foo, Formal theories of belief revision,Proc. 1st Int. Conf. on Principles of Knowledge Representation and Reasoning, Toronto (1989).
R. Reiter, A theory of diagnosis from first principles, Art. Int. (April 1987).
E. Sandewall, Filter preferential entailment for the logic of action in almost continuous worlds,Proc. Int. Joint Conf. on Artificial Intelligence, Detroit (August 1989).
K. Satoh, Nonmonotonic reasoning by minimal belief revision,Proc. Int. Conf. on Fifth Generation Computer Systems 1988, ICOT (December 1988).
Y. Shoham, A semantical approach to nonmonotonic logics, in:Readings in Nonmonotonic Reasoning, M.L. Ginsberg (ed.) (Morgan Kaufmann, Los Altos, 1987).
A. Van Gelder, Negation as failure using tight derivations for general logic programs, in:Foundations of Deductive Databases and Logic Programming, J. Minker (ed.) (Morgan Kaufmann, 1987).
A. Weber, Updating propositional formulas,Proc. Expert Database Systems Conf., Charleston, SC (April 1986).
M. Winslett, A framework for comparison of update semantics,Proc. 7th ACM Symp. on Principles of Database Systems (March 1988).
M. Winslett, Reasoning about action with a possible models approach,AAAI-88, Minneapolis (August 1988). A full version appears as TR UIUCDCS-R-88-1428, Department of Computer Science, Univ. of Illinois-Urbana (May 1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Winslett, M. Circumscriptive semantics for updating knowledge bases. Ann Math Artif Intell 3, 429–450 (1991). https://doi.org/10.1007/BF01530932
Issue Date:
DOI: https://doi.org/10.1007/BF01530932