×

Iterated belief revision, revised. (English) Zbl 1168.03318

Summary: The AGM postulates for belief revision, augmented by the DP postulates for iterated belief revision, provide widely accepted criteria for the design of operators by which intelligent agents adapt their beliefs incrementally to new information. These postulates alone, however, are too permissive: They support operators by which all newly acquired information is canceled as soon as an agent learns a fact that contradicts some of its current beliefs. In this paper, we present a formal analysis of the deficiency of the standard postulates alone, and we show how to solve the problem by an additional postulate of independence. We give a representation theorem for this postulate and prove that it is compatible with AGM and DP.

MSC:

03B42 Logics of knowledge and belief (including belief change)
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alchourrón, C. E.; Makinson, D., On the logic of theory change: contraction functions and their associated revision functions, Theoria, 48, 14-37 (1982) · Zbl 0525.03001
[2] Alchourrón, C. E.; Makinson, D., On the logic of theory change: safe contraction, Studia Logica, 44, 405-422 (1985) · Zbl 0605.03002
[3] Alchourrón, C. E.; Gärdenfors, P.; Makinson, D., On the logic of theory change: partial meet contraction and revision functions, Journal of Symbolic Logic, 50, 2, 510-530 (1985) · Zbl 0578.03011
[4] R. Booth, S. Chopra, T. Meyer, Restrained revision, in: Proceedings of the Sixth Workshop on Nonmonotonic Reasoning, Action and Change (NRAC), 2005; R. Booth, S. Chopra, T. Meyer, Restrained revision, in: Proceedings of the Sixth Workshop on Nonmonotonic Reasoning, Action and Change (NRAC), 2005 · Zbl 1182.68284
[5] Booth, R., A negotiation-style framework for non-prioritised revision, (Proceedings of Theoretical Aspects of Reasoning about Knowledge (TARK), vol. 8 (2001), Morgan Kaufmann), 137-150
[6] C. Boutilier, Revision sequences and nested conditionals, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1993, pp. 519-525; C. Boutilier, Revision sequences and nested conditionals, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1993, pp. 519-525
[7] Boutilier, C., Iterated revision and minimal change of conditional beliefs, Journal of Philosophical Logic, 25, 3 (1996) · Zbl 0858.03030
[8] Darwiche, A.; Pearl, J., On the logic of iterated belief revision, (Fagin, R., Proceedings of Theoretical Aspects of Reasoning about Knowledge (TARK) (1994), Morgan Kaufmann), 5-23
[9] Darwiche, A.; Pearl, J., On the logic of iterated belief revision, Artificial Intelligence, 89, 1-29 (1997) · Zbl 1018.03012
[10] Delgrande, J. P.; Dubois, D.; Lang, J., Iterated revision as prioritized merging, (Doherty, P.; Mylopoulos, J.; Welty, C. A., Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR) (2006), AAAI Press), 210-220
[11] Fariñas del Cerro, L.; Herzig, A., Belief change and dependence, (Shoham, Y., Proceedings of Theoretical Aspects of Reasoning about Knowledge (TARK) (1996), Morgan Kaufmann), 147-162
[12] Fermé, E. L.; Hansson, S. O., Selective revision, Studia Logica, 63, 3, 331-342 (1999) · Zbl 0942.03024
[13] M. Freund, D. Lehmann, Belief revision and rational inference, Technical Report TR-94-16, Institute of Computer Science, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel, 1994; M. Freund, D. Lehmann, Belief revision and rational inference, Technical Report TR-94-16, Institute of Computer Science, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel, 1994
[14] P. Gärdenfors, D. Makinson, Revisions of knowledge systems using epistemic entrenchment, in: Proceedings of Theoretical Aspects of Reasoning about Knowledge (TARK), Asilomar, CA, 1988, pp. 83-95; P. Gärdenfors, D. Makinson, Revisions of knowledge systems using epistemic entrenchment, in: Proceedings of Theoretical Aspects of Reasoning about Knowledge (TARK), Asilomar, CA, 1988, pp. 83-95 · Zbl 0711.03009
[15] Gärdenfors, P., Knowledge in Flux: Modeling the Dynamics of Epistemic States (1988), MIT Press · Zbl 1229.03008
[16] M. Goldszmidt, Qualitative probabilities: a normative framework for commonsense reasoning, PhD thesis, University of California at Los Angeles, 1992; M. Goldszmidt, Qualitative probabilities: a normative framework for commonsense reasoning, PhD thesis, University of California at Los Angeles, 1992
[17] Hansson, S. O., Revision of belief sets and belief bases, (Dubois, D.; Prade, H., Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 3: Belief Change (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 17-75 · Zbl 0937.03024
[18] Hansson, S. O., A survey of non-prioritized belief revision, Erkenntnis, 50, 413-427 (1999) · Zbl 0960.03012
[19] Hansson, S. O., Ten philosophical problems in belief revision, Journal of Logic and Computation, 13, 1, 37-49 (2003) · Zbl 1025.03012
[20] Jin, Y.; Thielscher, M., Representing beliefs in the fluent calculus, (de Mántaras, R. L.; Saitta, L., Proceedings of the European Conference on Artificial Intelligence (ECAI). Proceedings of the European Conference on Artificial Intelligence (ECAI), Valencia, Spain (August 2004), IOS Press), 823-827
[21] Y. Jin, M. Thielscher, Actions and belief revision: a computational approach, in: J. Delgrande, J. Lang, H. Rott, J. Tallon, (Eds.), Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, Dagstuhl Seminar 05321, 2005; Y. Jin, M. Thielscher, Actions and belief revision: a computational approach, in: J. Delgrande, J. Lang, H. Rott, J. Tallon, (Eds.), Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, Dagstuhl Seminar 05321, 2005
[22] Katsuno, H.; Mendelzon, A., On the difference between updating a knowledge base and revising it, (Allen, J. F.; Fikes, R.; Sandewall, E., Proceedings of Principles of Knowledge Representation and Reasoning (KR) (1991), Morgan Kaufmann), 387-394 · Zbl 0765.68197
[23] Katsuno, H.; Mendelzon, A. O., Propositional knowledge base revision and minimal change, Artificial Intelligence, 52, 3, 263-294 (1991) · Zbl 0792.68182
[24] Keller, A. M.; Winslett, M., On the use of an extended relational model to handle changing incomplete information, IEEE Transactions on Software Engineering, SE-11, 7, 620-633 (July 1985)
[25] Konieczny, S.; Pérez, R. P., A framework for iterated revision, Journal of Applied Non-Classical Logics, 10, 3-4 (2000)
[26] S. Konieczny, R.P. Pérez, Dynamical revision operators with memory, in: S. Benferhat, E. Giunchiglia (Eds.), Ninth International Workshop on Non-Monotonic Reasoning (NMR), 2002, pp. 171-179; S. Konieczny, R.P. Pérez, Dynamical revision operators with memory, in: S. Benferhat, E. Giunchiglia (Eds.), Ninth International Workshop on Non-Monotonic Reasoning (NMR), 2002, pp. 171-179
[27] D.J. Lehmann, Belief revision, revised, in: C.S. Mellish (Ed.), Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1995, pp. 1534-1540,; D.J. Lehmann, Belief revision, revised, in: C.S. Mellish (Ed.), Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1995, pp. 1534-1540,
[28] Nayak, A.; Foo, N.; Pagnucco, M.; Sattar, A., Changing conditional belief unconditionally, (Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge (TARK) (1996), Morgan Kaufmann), 119-135
[29] Nayak, A.; Nelson, P.; Polansky, H., Belief change as change in epistemic entrenchment, Synthese, 109, 143-174 (1996) · Zbl 0933.03012
[30] Nayak, A.; Pagnucco, M.; Peppas, P., Dynamic belief revision operators, Artificial Intelligence, 146, 2, 193-228 (2003) · Zbl 1082.03503
[31] Nayak, A., Iterated belief change based on epistemic entrenchment, Erkenntnis, 4, 353-390 (1994)
[32] Rott, H., A nonmonotonic conditional logic for belief revision, (Fuhrmann, A.; Morreau, M., The Logic of Theory Change (1991), Springer: Springer Berlin), 135-183 · Zbl 0925.03134
[33] Rott, H., Coherence and conservatism in the dynamics of belief. Part i: finding the right framework, Erkenntnis, 50, 387-412 (1999) · Zbl 0960.03013
[34] Rott, H., Two dogmas of belief revision, Journal of Philosophy, 97, 9, 503-522 (2000)
[35] Rott, H., Coherence and conservatism in the dynamics of belief II: iterated belief change without dispositional coherence, Journal of Logic and Computation, 13, 1, 111-145 (2003) · Zbl 1020.03015
[36] Spohn, W., Ordinal conditional functions: a dynamic theory of epistemic state, (Harper, W. L.; Skyrms, B., Causation in Decision: Belief, Change and Statistics: Proceedings of the Irvine Conference on Probability and Causation, vol. II (1988), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 105-134
[37] Spohn, W., A reason for explanation: explanations provide stable reasons, (Spohn, W.; etal., Existence and Explanation (1991), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 165-196
[38] Williams, M.-A., Two operators for theory bases, (Proceedings of the Australian Joint Artificial Intelligence Conference (1992), World Scientific), 259-265
[39] Williams, M.-A., Transmutations of knowledge systems, (Doyle, J.; Sandewall, E.; Torasso, P., Principles of Knowledge Representation and Reasoning (KR) (1994), Morgan Kaufmann), 619-629
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.