General Belief Revision

Abstract

In artificial intelligence, a key question concerns how an agent may rationally revise its beliefs in light of new information. The standard (AGM) approach to belief revision assumes that the underlying logic contains classical propositional logic. This is a significant limitation, since many representation schemes in AI don’t subsume propositional logic. In this article, we consider the question of what the minimal requirements are on a logic, such that the AGM approach to revision may be formulated. We show that AGM-style revision can be obtained even when extremely little is assumed of the underlying language and its semantics; in fact, one requires little more than a language with sentences that are satisfied at models, or possible worlds. The classical AGM postulates are expressed in this framework and a representation result is established between the postulate set and certain preorders on possible worlds. To obtain the representation result, we add a new postulate to the AGM postulates, and we add a constraint to preorders on worlds. Crucially, both of these additions are redundant in the original AGM framework, and so we extend, rather than modify, the AGM approach. As well, iterated revision is addressed and the Darwiche/Pearl postulates are shown to be compatible with our approach. Various examples are given to illustrate the approach, including Horn clause revision, revision in extended logic programs, and belief revision in a very basic logic called literal revision.

References

1. C.E. Alchourrón, P. Gärdenfors, and D. Makinson. 1985. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50, 2 (1985), 510--530.
2. A.R. Anderson and N.D. Belnap Jr. 1975. Entailment: The Logic of Relevance and Necessity, Vol. I. Princeton University Press, Princeton.
3. F. Baader, D. Calvanese, D. McGuiness, D. Nardi, and P. Patel-Schneider (Eds.). 2007. The Description Logic Handbook (2nd ed.). Cambridge University Press, Cambridge.
4. R. Baumann and G. Brewka. 2015. AGM meets abstract argumentation: expansion and revision for dung frameworks. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15). AAAI Press, 2734--2740.
5. Jonathan Ben-Naim. 2006. Lack of finite characterizations for the distance-based revision. In Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning, P. Doherty, J. Mylopoulos, and C. Welty (Eds.).
6. R. Booth, T. Meyer, and I.J. Varzinczak. 2009. Next steps in propositional horn contraction. In Proceedings of the International Joint Conference on Artificial Intelligence. 702--707.
7. R. Booth, T. Meyer, I. Varzinczak, and R. Wassermann. 2011. On the link between partial meet, kernel, and infra contraction and its application to horn logic. Journal of Artificial Intelligence Research 42 (2011), 31--53.
8. C. Boutilier. 1993. Revision sequences and nested conditionals. In Proceedings of the International Joint Conference on Artificial Intelligence. 519--531.
9. C. Boutilier. 1996. Iterated revision and minimal change of conditional beliefs. Journal of Logic and Computation 25 (1996), 262--305.
10. Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczyński. 2011. Answer set programming at a glance. Communications of the ACM 54, 12 (2011), 92--103.
11. Gerhard Brewka, Jean-Guy Mailly, and Stefan Woltran. 2016. Translation-based revision and merging for minimal horn reasoning. In Proceedings of the European Conference on Artificial Intelligence. IOS Press, 734--742.
12. P. Cabalar and P. Ferraris. 2007. Propositional theories are strongly equivalent to logic programs. Theory and Practice of Logic Programming 7, 6 (2007), 745--759.
13. S. Coste-Marquis, S. Konieczny, J.-G. Mailly, and P. Marquis. 2014. On the revision of argumentation systems: Minimal change of arguments statuses. In Proceedings of the 14th International Conference on the Principles of Knowledge Representation and Reasoning, Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter (Eds.). AAAI Press, 72--81.
14. N. Creignou, O. Papini, R. Pichler, and S. Woltran. 2014. Belief revision within fragments of propositional logic. Journal of Computer and System Sciences 80, 2 (2014), 427--449.
15. A. Darwiche and J. Pearl. 1997. On the logic of iterated belief revision. Artificial Intelligence 89 (1997), 1--29.
16. J. P. Delgrande. 2008. Horn clause belief change: Contraction functions. In Proceedings of the 11th International Conference on the Principles of Knowledge Representation and Reasoning, G. Brewka and J. Lang (Eds.). AAAI Press, Sydney, Australia, 156--165.
17. J. P. Delgrande and P. Peppas. 2011. Revising horn theories. In Proceedings of the International Joint Conference on Artificial Intelligence. 839--844.
18. J. P. Delgrande and P. Peppas. 2015. Belief revision in horn theories. Artificial Intelligence 218 (2015), 1--22. http://www.sciencedirect.com/science/article/pii/S0004370214001155.
19. J. P. Delgrande, P. Peppas, and S. Woltran. 2013. AGM-Style belief revision of logic programs under answer set semantics. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), Lecture Notes in Artificial Intelligence, P. Cabalar and T. C. Son (Eds.), Vol. 8148. Springer Verlag, 264--276.
20. J. P. Delgrande and R. Wassermann. 2013. Horn clause contraction functions. Journal of Artificial Intelligence Research 48 (November 2013), 475--511.
21. M. Diller, A. Haret, T. Linsbichler, S. Rümmele, and S. Woltran. 2018. An extension-based approach to belief revision in abstract argumentation. International Journal of Approximate Reasoning 93 (2018), 395--423.
22. P. M. Dung. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence 77, 2 (1995), 321--358.
23. T. Eiter, H. Tompits, and S. Woltran. 2005. On solution correspondences in answer set programming. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05). 97--102.
24. D. Gabbay, O. Rodrigues, and A. Russo. 2008. Belief revision in non-classical logics. The Review of Symbolic Logic 1 (2008), 267--304. Issue 03.
25. P. Gärdenfors. 1988. Knowledge in Flux: Modelling the Dynamics of Epistemic States. The MIT Press, Cambridge, MA.
26. M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub. 2012. Answer Set Solving in Practice. Morgan 8 Claypool Publishers.
27. M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium of Logic Programming (ICLP’88), R. Kowalski and K. Bowen (Eds.). The MIT Press, 1070--1080.
28. A. Grove. 1988. Two modellings for theory change. Journal of Philosophical Logic 17 (1988), 157--170.
29. S. O. Hansson. 1999. A Textbook of Belief Dynamics. Kluwer Academic Publishers.
30. H. Katsuno and A. Mendelzon. 1991. Propositional knowledge base revision and minimal change. Artificial Intelligence 52, 3 (1991), 263--294.
31. H. Katsuno and A. Mendelzon. 1992. On the difference between updating a knowledge base and revising it. In Belief Revision, P. Gärdenfors (Ed.). Cambridge University Press, Cambridge, 183--203.
32. S. Kraus, D. Lehmann, and M. Magidor. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44, 1--2 (1990), 167--207.
33. D. Lehmann, M. Magidor, and K. Schlechta. 2001. Distance semantics for belief revision. Journal of Symbolic Logic 66, 1 (2001), 295--317.
34. H.J. Levesque. 1998. A completeness result for reasoning with incomplete first-order knowledge bases. In Proceedings of the 6th International Conference on the Principles of Knowledge Representation and Reasoning, A. Cohn, L. Schubert, and S. Shapiro (Eds.). Morgan Kaufmann Publishers, 14--23.
35. D. Lewis. 1973. Counterfactuals. Harvard University Press, Cambridge, MA.
36. P. Peppas. 1996. Well behaved and multiple belief revision. In Proceedings of the 12th European Conference on Artificial Intelligence (ECAI’96). Wiley, 90--94.
37. P. Peppas. 2004. The limit assumption and multiple revision. Journal of Logic and Computation 14, 3 (2004), 355--371.
38. P. Peppas. 2008. Belief revision. In Handbook of Knowledge Representation, F. van Harmelen, V. Lifschitz, and B. Porter (Eds.). Elsevier Science, San Diego, 317--359.
39. G. Restall and J. K. Slaney. 1995. Realistic belief revision. In Proceedings of the 1st World Congress in the Fundamentals of Artificial Intelligence.
40. M. Ribeiro and R. Wassermann. 2014. Minimal change in AGM revision for non-classical logics. In Proceedings of the 14th International Conference on the Principles of Knowledge Representation and Reasoning. AAAI Press, Vienna, Austria, 657--660.
41. Karl Schlechta. 2004. Coherent Systems. Elsevier, Amsterdam.
42. N. Schwind and K. Inoue. 2013. Characterization theorems for revision of logic programs. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), Lecture Notes in Artificial Intelligence, P. Cabalar and T. C. Son (Eds.), Vol. 8148. Springer, 485--498.
43. B. Selman and H. Kautz. 1996. Knowledge compilation and theory approximation. J. ACM 43, 2 (1996), 193--224.
44. A. Tarski. 1936. On some fundamental concepts of metamathematics {1930}. In Logic, Semantics, Metamathematics. Papers from 1923 to 1938. Clarendon Press, Oxford, 30--36.
45. H. Turner. 2003. Strong equivalence made easy: Nested expressions and weight constraints. Theory and Practice of Logic Programming 3, 4 (2003), 609--622.
46. R. Wassermann. 2011. On AGM for non-classical logics. Journal of Philosophical Logic 40, 2 (2011), 271--294.
47. Jon Yaggie and György Turán. 2015. Characterizability in horn belief revision: An application of finite model theory. In Proceedings of the European Workshop on Logics in Artificial Intelligence (JELIA 2015) (Lecture Notes in Artificial Intelligence), Loizos Michael and Antonis C. Kakas (Eds.). Springer Verlag, 497--511.
48. D. Zhang and N. Foo. 2001. Infinitary belief revision. Journal of Philosophical Logic 30, 6 (2001), 525--570.
49. Z. Zhuang and Maurice Pagnucco. 2010. Horn contraction via epistemic entrenchment. In Logics in Artificial Intelligence—12th European Conference (JELIA’10), Lecture Notes in Artificial Intelligence, T. Janhunen and I. Niemelä (Eds.), Vol. 6341. Springer Verlag, 339--351.
50. Z. Zhuang and M. Pagnucco. 2011. Transitively relational partial meet horn contraction. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 1132--1138.
51. Z. Zhuang and M. Pagnucco. 2012. Model based horn contraction. In Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning. Rome, Italy, 169--178.
52. Z. Zhuang, M. Pagnucco, and Y. Zhang. 2013. Definability of horn revision from horn contraction. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1205--1211.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Nonmonotonic, default reasoning and belief revision

      • Reasoning about belief and knowledge

• Theory of computation

  • Logic