Skip to main content
SpringerLink
Log in

A model-based belief revision system

  • Published:
Journal of Automated Reasoning Aims and scope Submit manuscript

Abstract

Numerous belief revision and update semantics have been proposed in the literature in the past few years, but until recently, no work in the belief revision literature has focussed on the problem of implementing these semantics, and little attention has been paid to algorithmic questions. In this paper, we present and analyze our update algorithms built in Immortal, a model-based belief revision system. These algorithms can work for a variety of model-based belief revision semantics proposed to date. We also extend previously proposed semantics to handle updates involving the equality predicate and function symbols and incorporate these extensions in our algorithms. As an example, we discuss the use of belief revision semantics to model the action-augmented envisioning problem in qualitative simulation, and we show the experimental results of running an example simulation in Immortal.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abiteboul, S. and Grahne, G., ‘Update semantics for incomplete databases,’Proc. of the Conference on Very Large Data Bases, Stockholm, 1985.

  2. Bell, J., ‘Pragmatic logics,’Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, Mass., 1991, pp. 50–60.

  3. Boutilier, C., ‘Conditional logics of normality as modal systems,’Proceedings of the National Conference on Artificial Intelligence, Boston, Mass., 1990, pp. 594–599.

  4. Collins, J. W. and DeCoste, D., ‘CATMS: An ATMS which avoids label explosions,’Proceedings of the Ninth National Conference on Artificial Intelligence, Anaheim, Calif., 1991.

  5. Dalal, M., ‘Investigations into a theory of knowledge base revision: Preliminary report,’Proceedings of the Seventh National Conference on Artificial Intelligence, Minneapolis, 1988, pp. 475–479.

  6. de Kleer, J., ‘Exploiting locality in a TMS,’Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, 1990, pp. 264–271.

  7. del Val, A., ‘Computing knowledge base updates,’Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992.

  8. del Val, A. and Shoham, Y., ‘Deriving properties of belief update from theories of action (II),’Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, 1993.

  9. del Val, A., ‘Syntactic characterizations of belief change operators,’Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, 1993.

  10. del Val, A., Belief Revision and Update,' Ph.D. dissertation, Stanford University, 1993.

  11. Doyle, J., ‘A Truth Maintenance System,’Artificial Intelligence 12 (1979) 231–272.

    Google Scholar 

  12. Forbus, K. D., ‘Qualitative process theory,’Artificial Intelligence 24 (1984) 85–168.

    Google Scholar 

  13. Forbus, K. D., ‘Introducing actions into qualitative simulation,’Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, 1989, pp. 1273–1278.

  14. Freund, M., Lehmann, D. and Morris, P., ‘Rationality, transitivity, and contraposition,’Artificial Intelligence 52 no. 3 (1991) 191–203.

    Google Scholar 

  15. Friedrich, G., Gottlob, G. and Nejdl, W., ‘Generating efficient diagnostic procedures from model-based knowledge using logic programming techniques,’Computers and Mathematics with Applications 20, no. 9–10 (1990) 57–72.

    Google Scholar 

  16. Gärdenfors, P. and Makinson, D., ‘Revisions of knowledge systems using epistemic entrenchment,’Proceedings of the Second Conference on Theoretical Aspects of Reasoning About Knowledge, Asilomar, 1988, pp. 83–95.

  17. Gärdenfors, P.,Knowledge in Flux: Modeling the Dynamics of Epistemic States, Bradford Books, MIT Press, 1988.

  18. Gärdenfors, P., ‘The dynamics of belief systems: foundations vs. coherence theories,’Revue Internationale de Philosophie 44 (1990) 24–46.

    Google Scholar 

  19. Ginsberg, M. L. and Smith, D. E., ‘Reasoning about action I: A possible worlds approach,’ in Brown (ed.),The Frame Problem in Artificial Intelligence: Proceedings of the 1987 Workshop, Morgan Kaufmann Publishers, Los Altos, Calif., 1987, pp. 233–258.

    Google Scholar 

  20. Grahne, G., ‘Updates and counterfactuals,’Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, Mass., 1991, pp. 269–276.

  21. Grahne, G. and Mendelzon, A. O., ‘Updates and subjunctive queries,’ University of Toronto Technical Report KRR-TR-91-4, 1991;Information and Computation (to appear).

  22. Grahne, G., Mendelzon, A. O. and Reiter, R., ‘On the semantics of belief revision systems,’Proceedings of the Conference on Theoretical Aspects of Reasoning about Knowledge, 1992.

  23. Hegner, S., ‘Specification and implementation of programs for updating incomplete information databases,’Proceedings of the Sixth Symposium on Principles of Database Systems, San Diego, 1987, pp. 146–158.

  24. Katsuno, H. and Mendelzon, A. O., ‘A unified view of propositional knowledge base updates,’Proceedings of the International Joint Conference on Artificial Intelligence, Detroit, 1989.

  25. Katsuno, H. and Mendelzon, A. O., ‘Propositional knowledge base revision and minimal change,’ Technical Reports on KR & R, Computer Science Department, University of Toronto, KRR-TR-90-3, 1990.

  26. Katsuno, H. and Mendelzon, A. O., ‘On the difference between updating a knowledge base and revising it,’Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, Mass., 1991, pp. 387–394.

  27. Katsuno, H. and Satoh, K., ‘A unified view of consequence relation, belief revision and conditional logic,’Proceedings of the International Joint Conference on Artificial Intelligence, Sidney, Australia, 1991, pp. 406–412, Morgan Kaufmann.

  28. Keller, A. M. and Winslett, M., ‘On the use of an extended relational model to handle changing incomplete information,’IEEE Transactions on Software Engineering SE-11(7) (1985) 620–633.

    Google Scholar 

  29. Lehmann, D., ‘What does a conditional knowledge base entail?’Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, 1989, pp. 212–222.

  30. Lin, F. and Shoham, Y., ‘Provably correct theories of action (preliminary report),’Proceedings of the Tenth National Conference on Artificial Intelligence, Anaheim, Calif., 1991.

  31. Makinson, D., ‘General theory of cumulative inference,’Non-Monotonic Reasoning, Springer-Verlag Lecture Notes on Artificial Intelligence, No. 346, 1989.

  32. Myers, K. and Smith, D. E., ‘On the persistence of derived information,’National Conference on Artificial Intelligence, Minneapolis, 1988.

  33. Nejdl, W., ‘The P-systems: A systematic classification of logics of non-monotonicity,’Proceedings of the National Conference on Artificial Intelligence, Anaheim, Calif., 1991, pp. 366–372.

  34. Pfau, M. and Nejdl, W., ‘Integrating model-based and heuristic features in a realtime expert system for power distribution networks,’ 1991 (submitted).

  35. Rao, A. S. and Foo, N. Y., ‘Minimal change and maximal coherence: A basis for belief revision and reasoning about actions,’Proceedings of the International Joint Conference on Artificial Intelligence, Detroit, 1989.

  36. Rao, A. S. and Foo, N. Y., ‘Formal theories of belief revision,’ in R. J. Brachman, H. J. Levesque and R. Reiter (eds.),Principles of Knowledge Representation and Reasoning: Proceedings of the First International Conference, San Mateo, Calif., Morgan Kaufmann, 1989.

    Google Scholar 

  37. Reiter, R., ‘A theory of diagnosis from first principles,’Artificial Intelligence, 1987.

  38. Sandewall, E., ‘Filter preferential entailment for the logic of action in almost continuous worlds,’Proceedings of the International Joint Conference on Artificial Intelligence, Detroit, 1989.

  39. Satoh, K., ‘Nonmonotonic reasoning by minimal belief revision,’Proceedings of the International Conference on Fifth Generation Computer Systems 1988, ICOT, 1988, pp. 455–462.

  40. Weber, A., ‘Updating propositional formulas,’Proceedings of the First International Expert Database Systems Conference, Charleston, S.C., 1986, pp. 487–500.

  41. Winslett, M., ‘A framework for comparison of update semantics,’Proceedings of the 7th ACM Symposium on Principles of Database Systems, 1988.

  42. Winslett, M., ‘Reasoning about action using a possible models approach,’Proceedings of the Seventh National Conference on Artificial Intelligence, Minneapolis, 1988, pp. 89–93.

  43. Winslett, M. and Chou, T., ‘Updates with equality: Beyond the Herbrand universe assumption,’Proceedings of 6th Int'l Symposium on Methodologies for Intelligent Systems, Charlotte, N.C., 1991, pp. 276–285.

Download references

Author information

Authors and Affiliations

  1. Department of Information Management, National Taiwan University, Taipei, Taiwan, Republic of China

    Timothy S. C. Chou

  2. Department of Computer Science, University of Illinois, 1304 W Springfield, 61801, Urbana, IL, USA

    Marianne Winslett

Authors
  1. Timothy S. C. Chou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marianne Winslett
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chou, T.S.C., Winslett, M. A model-based belief revision system. J Autom Reasoning 12, 157–208 (1994). https://doi.org/10.1007/BF00881886

Download citation

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00881886

Key words

Search

Navigation