Abstract
We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts declared “persistent by default”. The focus of the paper is on the relation between this approach and the update semantics recently proposed by Katsuno and Mendelzon. Our contribution in this regard is twofold:
-
We prove a representation theorem for KM semantics in terms of a restricted subfamily of the operators defined by our construction.
-
We show how the KM semantics can be generalized by relaxing our construction in a number of ways, each justified in certain intuitive circumstances and each corresponding to one specific postulate. It follows that there are reasonable update operators outside the KM family.
-
Our approach is not dependent for its plausibility on this connection with KM semantics. Rather, it provides a relatively rich and flexible framework in which the frame and ramification problems can be solved in a systematic way by reasoning about default persistence of facts.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alchourrón, C.E., Gärdenfors, P. and Makinson, D., 1985, “On the logic of theory change: Partial meet functions for contraction and revision”,Journal of Symbolic Logic 50, 510–530.
del Val, A, and Shoham, Y., 1992, “Deriving properties of belief update from theories of action”, inProceedings of the Tenth Conference of the AAAI, AAAI Press, Menlo Park, CA, 584–589.
del Val, A. “Belief Revision and Update”, Ph.D. thesis. Stanford University, march 1993.
del Val, A. and Shoham, Y., 1994. “A unified view of belief revision and updata”.Journal of logic and computation (in press).
Etherington, D.W., Mercer, R.E. and Reiter, R., 1985, “On the adequacy of predicate circumscription for closed world reasoning”,Computational Intelligence 1, 11–15.
Gärdenfors, P., 1988,Knowledge in Flux: Modeling the Dynamics of Epistemic States, Cambridge, MA: The MIT Press, Bradford Books.
Goldszmidt, M. and Pearl, J., 1992, “Rank-based systems: A simple approach to belief revision, belief update and reasoning about evidence and actions”, inProceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR'92), Nebel, B., Rich, C, and Swartout, W. (eds.) Morgan Kaufmann, San Mateo, CA, 661–672.
Katsuno, H. and Mendelzon, A.O., 1989, “A unified view of propositional knowledge base updates”, inProceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI Inc. Menlo Park, CA, 406–412.
Katsuno, H. and Mendelzon, A.O., 1991, “On the difference between updating a knowledge database and revising it”, inProceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR'91), Allen, J., Fikes, R., Sandewall, E. (eds.), Morgan Kaufmann, San Mateo, CA, 387–394.
Lifschitz, V., 1986, “On the satisfiability of circumscription”,Artificial Intelligence 28, 17–27.
Lifschitz, V., 1990, “Frames in the space of situations”,Artificial Intelligence 46, 365–376.
Lin, F. and Shoham, Y., 1991, “Provably correct theories of action (preliminary report)”, inProceedings of the Ninth Conference of the AAAI, AAAI Press, Menlo Park, CA, 349–354.
Lin, F. and Shoham, Y, 1992, “Current actions in situation calculus”, inProceedings of the Tenth Conference of the AAAI, AAAI Press, Menlo Park, CA, 590–595.
Myers, K.L. and Smith, D.E., 1988, “The persistence of derived information”, inProceedings of the Seventh Conference of the AAAI, AAAI Press, Menlo Park, CA, 496–500.
Reiter, R.R., 1992a, “On specifying database updates”,Technical Report KRR-TR-92-5, Computer Science Department, University of Toronto.
Reiter, R.R., 1992b, “On formalizing database updates: Preliminary report”, inProceedings of the Third International Conference on Extending Database Technology.
Schubert, L.K., 1990, “Monotonic solution of the frame problem in situation calculus: An efficient method for worlds with fully specified actions”, inKnowledge Representation and Defeasible Reasoning, Kyberg, H.E., Loui, R.P. and Carlson, G.N., (eds.), Dordrecht, Kluwer Academic Publishers, 23–67.
Winslett, M., 1988, “Reasoning about action using a possible models approach”, inProceedings of the Seventh Conference of the AAAI, AAAI Press, Menlo Park, CA, 89–93.
Winslett, M., 1989, “Sometimes updates are circumscription”, inProceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI Inc. Menlo Park, CA, 859–863.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Del Val, A., Shoham, Y. Deriving properties of belief update from theories of action. J Logic Lang Inf 3, 81–119 (1994). https://doi.org/10.1007/BF01110611
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01110611