Skip Navigation



Journal of Logic and Computation Advance Access published online on April 10, 2008
Journal of Logic and Computation, doi:10.1093/logcom/exm094
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Jin, Y.
Right arrow Articles by Thielscher, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Reinforcement Belief Revision

Yi Jin

School of Computing Science, Simon Fraser University, Burnaby, Canada E-mail: yij{at}cs.sfu.ca

Michael Thielscher

Department of Computer Science, Dresden University of Technology, Dresden, Germany E-mail: mit{at}inf.tu-dresden.de

The capability of revising its beliefs upon new information in a rational and efficient way is crucial for an intelligent agent. The classical work in belief revision focuses on idealized models and is not concerned with computational aspects. In particular, many researchers are interested in the logical properties (e.g. the AGM postulates) that a rational revision operator should possess. For the implementation of belief revision, however, one has to consider that any realistic agent is a finite being and that calculations take time. In this article, we introduce a new operation for revising beliefs which we call reinforcement belief revision. The computational model for this operation allows us to assess it in terms of time and space consumption. Moreover, the operation is proved equivalent to a (semantical) model based on the concept of possible worlds, which facilitates showing that reinforcement belief revision satisfies all desirable rationality postulates.

Keywords: Iterated belief revision; computational revision operators; reinforcement effect; implicit dependence; possibilistic logic



References

  1. Alchourrón CE, Gärdenfors P, Makinson D. On the logic of theory change: partial meet contraction and revision functions. The Journal of Symbolic Logic (1985) 50:510–530.[CrossRef]
  2. Alchourrón CE, Makinson D. On the logic of theory change: safe contraction. Studia Logica (1985) 44:405–422.[CrossRef]
  3. Benferhat S, Dubois D, Prade H, Williams M-A. A practical approach to revising prioritized knowledge bases. Studia Logica (2002) 70:105–130.[CrossRef]
  4. Boutilier C. Revision sequences and nested conditionals. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (1993) France: Morgan Kaufmann, Chambéry. 519–525.
  5. Cadoli M, Donini FM, Liberatore P, Schaerf M. The size of a revised knowledge base. In: PODS '95: Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (1995) New York, NY, USA: ACM Press. 151–162.
  6. Dalal M. Updates in propositional databases. In: Technical Report DCS-TR 222 (1988) February. Rutgers University, Department of Computer Science.
  7. Darwiche A, Pearl J. On the logic of iterated belief revision. Artificial Intelligence (1997) 89:1–29.[CrossRef][ISI]
  8. Dixon SE. Belief revision: a computational approach. (1994) Australia: Basser Department of Computer Science, University of Sydney. PhD Thesis.
  9. Dubois D, Lang J, Prade H. Possibilistic logic. In: Handbook of Logic in Artificial Intelligence and Logic Programming (vol. 3): Nonmonotonic Reasoning and Uncertain Reasoning (1994) New York, NY, USA: Oxford University Press, Inc. 439–513.
  10. Dubois D, Moral S, Prade H. Belief change rules in ordinal and numerical uncertainty theories. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems—Gabbay DM, Smets P, eds. (1998) Vol. 3. Dordrecht: Kluwer Academic Publishers. 311–392.
  11. Dubois D, Prade H. Epistemic entrenchment and possibilistic logic. Artificial Intelligence (1991) 50:223–239.[CrossRef][ISI]
  12. Dubois D, Prade H. Belief change and possibility theory. In: Belief Revision—Gärdenfors P, ed. (1992) Cambridge, UK: Cambridge University Press. 142–182.
  13. Eiter T, Gottlob G. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence (1992) 57:227–270.[CrossRef][ISI]
  14. Gärdenfors P. Knowledge in Flux: Modeling the Dynamics of Epistemic States. (1988) Cambridge, Massachusetts (USA): MIT Press.
  15. Gärdenfors P, Makinson D. Revisions of knowledge systems using epistemic entrenchment. In: Proceedings of the Second Conference on Theoretical Aspects of Reasoning about Knowledge (TARK) (1988) Asilomar, CA: MorganKaufmann. 83–95.
  16. Goldszmidt M. Qualitative probabilities: a normative framework for commonsense reasoning. (1992) University of California at Los Angeles. PhD Thesis.
  17. Hansson SO. Ten philosophical problems in belief revision. Journal of Logic Computation (2003) 13:37–49.[CrossRef]
  18. Jeffrey RC. The Logic of Decision. (1965) New York: University of Chicago Press.
  19. Jin Y, Thielscher M. Iterated belief revision, revised. Artificial Intelligence (2007) 171:1–18.[CrossRef][ISI]
  20. Katsuno H, Mendelzon AO. Propositional knowledge base revision and minimal change. Artificial Intelligence (1991) 52:263–294.[CrossRef][ISI]
  21. Katsuno H, Satoh K. A unified view of consequence relation, belief revision and conditional logic. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (1991) Sydney, Australia: Morgan Kaufmann. 406–412.
  22. Konieczny S, Pérez RP. A framework for iterated revision. Journal of Applied Non-Classical Logics (2000) 10:339–367.
  23. Liberatore P. The complexity of belief update. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI '97) (1997) Nagoya, Japan: Morgan Kaufmann. 68–73.
  24. Liberatore P. The complexity of iterated belief revision. In: Proceeding of the 6th International Conference on Database Theory (ICDT)—Afrati FN, Kolaitis PG, eds. (1997) Delphi, Greece: Springer. 276–290.
  25. Nayak A. Iterated belief change based on epistemic entrenchment. Erkenntnis (1994) 4:353–390.
  26. Nayak A, Foo N, Pagnucco M, Sattar A. Changing conditional belief unconditionally. In: Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge (TARK) (1996) San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. 119–135.
  27. Nayak A, Pagnucco M, Peppas P. Dynamic belief revision operators. Artificial Intelligence (2003) 146:193–228.[CrossRef][ISI]
  28. Nebel B. Belief revision and default reasoning: Syntax-based approaches. In: Principles of Knowledge Representation and Reasoning: Proceedings of the 2nd International Conference—Allen JA, Fikes R, Sandewall E, eds. (1991) San Mateo: Morgan Kaufmann. 417–428.
  29. Nebel B. Syntax-based approaches to belief revision. In: Belief Revision—Gärdenfors P, ed. (1992) Vol. 29. Cambridge, UK: Cambridge University Press. 52–88.
  30. Nebel B. Base revision operations and schemes: Semantics, representation and complexity. In: Proceedings of the European Conference on Artificial Intelligence (ECAI) (1994) Amsterdam, The Netherlands: John Wiley and Sons. 341–345.
  31. Nebel B. How hard is it to revise a belief base? In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 3: Belief Change—Dubois D, Prade H, eds. (1998) Dordrecht: Kluwer Academic Publishers. 77–145.
  32. Newell A. The knowledge level. Artificial Intelligence (1982) 18:87–127.[CrossRef][ISI]
  33. Papadimitriou C. Computational Complexity. (1994) Massachusetts (USA): Addison-Wesley, Reading.
  34. Spohn W. Ordinal conditional functions: A dynamic theory of epistemic state. In: Causation in Decision: Belief, Change and Statistics: Proceedings of the Irvine Conference on Probability and Causation—Harper WL, Skyrms B, eds. (1988) Vol. II. Dordrecht: Kluwer Academic Publisher. 105–134.
  35. Spohn W. A reason for explanation: explanations provide stable reasons. In: Existence and Explanation—Spohn W, et al, eds. (1991) Dordrecht, The Netherlands: Kluwer Academic Publisher. 165–196.
  36. Wassermann R. Resource-Bounded Belief Revision. (1999) ILLC, University of Amsterdam. PhD Thesis.
  37. Williams M. Proceedings of the Fifth Australian Joint Conference on Artificial Intelligence. (1992) Hobart, Australia: World Scientific. 259–265.
  38. Williams M-A. Transmutations of knowledge systems. In: Principles of Knowledge Representation and Reasoning (KR)—Doyle J, Sandewall E, Torasso P, eds. (1994) Bonn, Germany: Morgan Kaufmann. 619–629.
  39. Wobcke WR. On the use of epistemic entrenchment in nonmonotonic reasoning. In: Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI) (1992) Vienna, Austria: John Wiley and Sons. 324–328.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Jin, Y.
Right arrow Articles by Thielscher, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?