Abstract
We present a formal framework for theory revision that is based on a tableaux algorithm. We use a semantic tableaux system for generating the tableau of a belief base and of a revision formula. Specific revision operators can then be defined in terms of tableaux branches. Tableaux branches of a formula correspond to implicants of the formula. We define a new set of revision postulates for implicant sets and we show that they verify the AGM revision postulates. Then we consider specific distance based revision operators and in particular those based on the symmetrical difference between interpretations. We show that the minimal symmetric difference between the model sets of two implicants can be obtained by a simple binary operation on these implicants. Finally, we define three specific distance based revision operators. The representation of a formula by implicants is not unique (our approach is not based on prime implicants). We show that our implicant revision approach obtains the same revision result operated on different equivalent implicant sets for the three revision operators we propose.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Proceedings of the 7th National Conference on Artificial Intelligence (1988)
Alchourron, C.E., Gärdenfors, V., Makinson, D.: On the logic of theory change: Partial meet contradictions and revision functions. Journal of Symbolic Logic 50(2), 510–530 (1985)
Allen, J.A., Fikes, R., Sandewall, E. (eds.): Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (1991)
Beth, E.W.: The Foundations of Mathematics. North Holland, Amsterdam (1959)
Bienvenu, M., Herzig, A., Qi, G.: Prime implicate-based belief revision operators. In: Ghallab, M., Spyropoulos, C.D., Fakotakis, N., Avouris, N.M. (eds.) ECAI. Frontiers in Artificial Intelligence and Applications, vol. 178, pp. 741–742. IOS Press, Amsterdam (2008)
Bordiga, A.: Language features for flexible handling of exceptions in information systems. ACM Transactions on Database Systems 10, 563–603 (1985)
Dalal, M.: Investigations into a theory of knowledge base revision. In: AAAI 1988 [1], pp. 475–479 (1988)
Darwiche, A., Pearl, J.: On the logic of iterated belief revision. Artificial Intelligence 89(1-2), 1–29 (1997)
Delgrande, J.P., Jin, Y., Pelletier, F.J.: Compositional belief update. J. Artif. Intell. Res. (JAIR) 32, 757–791 (2008)
Eiter, T., Gottlob, G.: On the complexity of propositional knowledge base revision, updates and counterfacts. Artificial Intelligence 57, 227–270 (1992)
Fitting, M.: First Order Logic and Automated Theorem Proving. Texts and Monographs in Computer Science. Springer, Heidelberg (1990)
Gärdenfors: Knowledge in Flux: Modeling the Dynamics of Epistemic States. Bradford Books. MIT Press, Cambridge (1988)
Katsuno, H., Mendelzon, A.O.: On the difference between updating a knowledge base and revising it. In: Allen et al. [3], pp. 387–394
Katsuno, H., Mendelzon, A.O.: Propositional knowledge base revision and minimal change. Artificial Intelligence 52, 263–294 (1991)
Konieczny, S., Pérez, R.P.: On the logic of merging. In: KR 1998, pp. 488–498 (1998)
Lehmann, D.J., Magidor, M., Schlechta, K.: Distance semantics for belief revision. J. Symb. Log. 66(1), 295–317 (2001)
Perrussel, L., Marchi, J., Bittencourt, G.: Une nouvelle mesure de changement minimal. In: RFIA (ed.) RFIA 2006 Proceedings Électroniques (2006)
Perrussel, L., Marchi, J., Bittencourt, G.: Prime implicants and belief update. In: Chad Lane, H., Guesgen, H.W. (eds.) FLAIRS Conference. AAAI Press, Menlo Park (2009)
Satoh, K.: Nonmonotonic reasoning by minimal belief revision. In: Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, pp. 455–462 (1988)
Schlechta, K.: Coherent Systems. Studies in Logic and Practical Reasoning, vol. (2). Elsevier, Amsterdam (2004)
Smullyan, R.M.: First Order Logic. Springer, Heidelberg (1968)
Williams, M.-A.: Transmutations of knowledge systems. In: Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning, pp. 619–629 (1994)
Winslett, M.: Reasoning about action with a possible models approach. In: AAAI 1988 [1], pp. 89–93 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schwind, C. (2010). From Inconsistency to Consistency: Knowledge Base Revision by Tableaux Opening. In: Kuri-Morales, A., Simari, G.R. (eds) Advances in Artificial Intelligence – IBERAMIA 2010. IBERAMIA 2010. Lecture Notes in Computer Science(), vol 6433. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16952-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-16952-6_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16951-9
Online ISBN: 978-3-642-16952-6
eBook Packages: Computer ScienceComputer Science (R0)