research-article

General Belief Revision

Authors:

James P. Delgrande,

Stefan WoltranAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 5

Article No.: 29, Pages 1 - 34

https://doi.org/10.1145/3203409

Published: 07 September 2018 Publication History

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.

Digital Library

[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.

Digital Library

[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.).

Digital Library

[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.

Digital Library

[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.

Digital Library

[8]

C. Boutilier. 1993. Revision sequences and nested conditionals. In Proceedings of the International Joint Conference on Artificial Intelligence. 519--531.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[15]

A. Darwiche and J. Pearl. 1997. On the logic of iterated belief revision. Artificial Intelligence 89 (1997), 1--29.

Digital Library

[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.

Digital Library

[17]

J. P. Delgrande and P. Peppas. 2011. Revising horn theories. In Proceedings of the International Joint Conference on Artificial Intelligence. 839--844.

Digital Library

[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.

Digital Library

[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.

Digital Library

[20]

J. P. Delgrande and R. Wassermann. 2013. Horn clause contraction functions. Journal of Artificial Intelligence Research 48 (November 2013), 475--511.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[30]

H. Katsuno and A. Mendelzon. 1991. Propositional knowledge base revision and minimal change. Artificial Intelligence 52, 3 (1991), 263--294.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[43]

B. Selman and H. Kautz. 1996. Knowledge compilation and theory approximation. J. ACM 43, 2 (1996), 193--224.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Olivieri FCristani MGovernatori GPasetto LRotolo AScannapieco STomazzoli CChekole Workneh T(2024)Revising non-monotonic theories with sufficient and necessary conditions: the case of Defeasible LogicJournal of Logic and Computation10.1093/logcom/exae044Online publication date: 6-Sep-2024
https://doi.org/10.1093/logcom/exae044
Guimarães ROzaki ARibeiro JWilliams BChen YNeville J(2023)Finite based contraction and expansion via modelsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25786(6389-6397)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25786
Bonanno G(2022)Filtered Belief Revision: Syntax and SemanticsJournal of Logic, Language and Information10.1007/s10849-022-09374-x31:4(645-675)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10849-022-09374-x
Show More Cited By

Index Terms

General Belief Revision
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Nonmonotonic, default reasoning and belief revision
      2. Reasoning about belief and knowledge
2. Theory of computation
  1. Logic

Recommendations

Revocable Belief Revision

Krister Segerberg proposed irrevocable belief revision, to be contrasted with standard belief revision, in a setting wherein belief of propositional formulas is modelled explicitly. This suggests that in standard belief revision is revocable: one should ...
Relevance in belief revision

Possible-world semantics are provided for Parikh's relevance-sensitive axiom for belief revision, known as axiom (P). Loosely speaking, axiom (P) states that if a belief set K can be divided into two disjoint compartments, and the new information ...
A belief revision framework for revising epistemic states with partial epistemic states

Belief revision performs belief change on an agent's beliefs when new evidence (either of the form of a propositional formula or of the form of a total pre-order on a set of interpretations) is received. Jeffrey's rule is commonly used for revising ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 5

October 2018

299 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3274534

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 September 2018

Accepted: 01 March 2018

Revised: 01 April 2017

Received: 01 August 2016

Published in JACM Volume 65, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Natural Sciences and Engineering Research Council of Canada
Austrian Science Fund (FWF)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Olivieri FCristani MGovernatori GPasetto LRotolo AScannapieco STomazzoli CChekole Workneh T(2024)Revising non-monotonic theories with sufficient and necessary conditions: the case of Defeasible LogicJournal of Logic and Computation10.1093/logcom/exae044Online publication date: 6-Sep-2024
https://doi.org/10.1093/logcom/exae044
Guimarães ROzaki ARibeiro JWilliams BChen YNeville J(2023)Finite based contraction and expansion via modelsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25786(6389-6397)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25786
Bonanno G(2022)Filtered Belief Revision: Syntax and SemanticsJournal of Logic, Language and Information10.1007/s10849-022-09374-x31:4(645-675)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10849-022-09374-x
Falakh FRudolph SSauerwald K(2022)Semantic Characterizations of AGM Revision for Tarskian LogicsRules and Reasoning10.1007/978-3-031-21541-4_7(95-110)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21541-4_7
Tardivo FPham LSon TPontelli E(2021)A Logic Programming Approach to Regression Based Repair of Incorrect Initial Belief StatesPractical Aspects of Declarative Languages10.1007/978-3-030-67438-0_5(73-89)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67438-0_5
Zhuang ZWang ZWang KDelgrande J(2019)A generalisation of AGM contraction and revision to fragments of first-order logicJournal of Artificial Intelligence Research10.1613/jair.1.1133764:1(147-179)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11337

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents