Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Combining nonmonotonic reasoning and belief revision: A practical approach

  • Conference paper
  • First Online:
Artificial Intelligence: Methodology, Systems, and Applications (AIMSA 1998)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1480))

Abstract

In this paper, a new syntax-based approach to belief revision is presented. It is developed within a nonmonotonic framework that allows a two-steps handling of inconsistency to be adopted. First, a disciplined use of non-monotonic ingredients is made available to the knowledge engineer to prevent many inconsistencies that would occur if a standard logical interpretation and representation of beliefs were conducted. Remaining inconsistencies are considered unexpected and revised by weakening the formulas occurring in any minimally inconsistent subbase, as if they were representing exceptional cases that do not actually occur. While the computation of revised knowledge bases remains intractable in the worst case, our approach benefits from an efficient local search-based heuristic technique that empirically proves often viable, even in the context of very large prepositional applications.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Alchourrón, C., Gärdenfors, P., Makinson, D.: On the logic of theory change: partial meet functions for contraction and revision. Journ. of Symbolic Logic, vol. 50, pp. 510–530 (1985)

    Article  MATH  Google Scholar 

  2. Benfherat, S., Dubois, D., Prade, H.: How to infer from inconsistent beliefs without revising. Proc. IJCAI-95, pp. 1449–1455 (1995)

    Google Scholar 

  3. Cadoli, M., Donini, F., Liberatore, P., Schaerf, M.: The size of a revised knowledge base. Proc. PODS-95, pp. 151–162 (1995)

    Google Scholar 

  4. Darwiche, A., Pearl, J.: On the logic of iterated belief revision. Artificial Intelligence, vol. 89, pp. 1–30 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  5. del Val, A.: On the relation between the coherence and foundations theories of belief revision. Proc. AAAI-94, pp. 909–914 (1994)

    Google Scholar 

  6. DIMACS 93: Second SAT challenge organized by the Center for Discrete Mathematics and Computer Science of Rutgers University (1993)

    Google Scholar 

  7. Eiter, T., Gottlob, G.: On the complexity of prepositional knowledge base revision, updates, and counterfactual. Artificial Intelligence, vol. 57, pp. 227–270 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fagin, R., Ullman, J.D., Vardi, M.Y.: On the semantics of updates in databases. Proc. PODS-83, pp. 352–365 (1983)

    Google Scholar 

  9. Friedman, N., Halpern, J.Y.: Belief revision: a critique. Proc. KR'96, pp. 429–431 (1996)

    Google Scholar 

  10. Gärdenfors, P.: Belief revision and nonmonotonic logic: Two sides of the same coin?. Proc. ECAI92, Pitman Publishing, pp. 768–773 (1992)

    Google Scholar 

  11. Kautz, H., Selman, B.: Pushing the envelope: planning, prepositional logic, and stochastic search. Proc. AAAI-96, pp. 1194–1201, Portland (1996)

    Google Scholar 

  12. Lehman, D.: Belief revision revisited. Proc. IJCAI-95, pp. 1534–1540 (1995)

    Google Scholar 

  13. Liberatore, P., Schaerf, M.: Relating belief revision and circumscription. Proc. IJCAI-95, pp. 1557–1553 (1995)

    Google Scholar 

  14. Liberatore, P., Schaerf, M.: The complexity of model checking for belief revision and update. Proc. AAAI-96, pp. 556–561 (1996)

    Google Scholar 

  15. Makinson, D., Gärdenfors, P.: Relations between the logic of theory change and nonmonotonic logic. In: Fuhrmann and Morreau (eds), Proc. of the Workshop on the logic of theory change, LNCS 465, Springer, pp. 185–205 (1991)

    Google Scholar 

  16. Mazure, B., SaÏs, L., Grégoire, E.: Detecting logical inconsistencies. Proc. AI and Maths Symposium, Fort Lauderdale (FL), pp. 116–121. (1996) (extended version in Annals of AI & Maths (in print))

    Google Scholar 

  17. Mazure, B., SaÏs, L., Grégoire, E.: Tabu search for SAT. Proc. AAAI-97, pp. 281–285 (1997)

    Google Scholar 

  18. McCarthy J.: Applications of circumscription to formalizing common-sense knowledge. Artificial Intelligence, vol. 28, pp. 89–116 (1986)

    Article  MathSciNet  Google Scholar 

  19. Moinard Y.: Revision and nonmonotonicity. Int. Journ. of Intelligent Systems, vol. 9 (1994)

    Google Scholar 

  20. Morris P.: The breakout method for escaping from local minima. Proc. AAAI-93 (1993)

    Google Scholar 

  21. Nebel B.: A knowledge level analysis of belief revision. Proc. KR-89, pp. 301–311 (1989)

    Google Scholar 

  22. Nebel B.: Syntax-based approaches to belief revision. In: Gärdenfors P. (ed), Belief Revision, Cambridge University Press, pp. 53–88 (1992)

    Google Scholar 

  23. Nebel B.: How hard is it to revise a belief base?. report 83, Institut für Informatik, Albert-Ludwigs-Universität Freiburg, Freiburg (1996)

    Google Scholar 

  24. Newell A.: The knowledge level. Artificial Intelligence, vol. 18, pp. 87–127 (1982)

    Article  Google Scholar 

  25. Papini O.: Revision in prepositional calculus. Proc. ECSQAU91, Marseille, LNCS 548, Springer, pp. 272–276 (1991)

    Google Scholar 

  26. Selman, B., Kautz, H.: An empirical study of greedy local search for satisfiability testing“. Proc. AAAI-93 (1993)

    Google Scholar 

  27. Selman, B., Levesque, H., Mitchell, D.: A New Method for Solving Hard Satisfiability Problems. Proc. AAAI-92, pp. 440–446 (1992)

    Google Scholar 

  28. Selman, B., Kautz, H.A., Cohen, B.: Local Search Strategies for Satisfiability Testing. Proc. 1993 DIMACS Workshop on Maximum Clique, Graph Coloring, and Satisfiability (1993)

    Google Scholar 

  29. Selman, B., Kautz, H., McAllester, D.: Computational Challenges in Propositional Reasoning and Search. Proc. IJCAI-97 (1997)

    Google Scholar 

  30. Shoham, Y.: A semantical approach to non-monotonic logics. In: Ginsberg M.L. (ed.), Readings in Non-Monotonic Reasoning, Morgan Kaufmann (1987)

    Google Scholar 

  31. Williams, M.A.: Iterated Theory Base Change: a computational model. Proc. IJCAI-95, pp. 1541–1550 (1995)

    Google Scholar 

  32. Winslett, M.: Updating Logical Databases. Cambridge University Press (1990)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. C.R.I.L. Université d'Artois, Rue de l'Université SP16, F-62307, Lens Cedex, France

    Brigitte Bessant, Eric Grégoire, Pierre Marquis & Lakhdar SaÏs

Authors
  1. Brigitte Bessant
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eric Grégoire
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pierre Marquis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lakhdar SaÏs
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Fausto Giunchiglia

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bessant, B., Grégoire, E., Marquis, P., SaÏs, L. (1998). Combining nonmonotonic reasoning and belief revision: A practical approach. In: Giunchiglia, F. (eds) Artificial Intelligence: Methodology, Systems, and Applications. AIMSA 1998. Lecture Notes in Computer Science, vol 1480. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057439

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64993-9

  • Online ISBN: 978-3-540-49793-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation