article

A generalisation of AGM contraction and revision to fragments of first-order logic

Authors:

Zhiqiang Zhuang,

James DelgrandeAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 64, Issue 1

Pages 147 - 179

https://doi.org/10.1613/jair.1.11337

Published: 01 January 2019 Publication History

Abstract

AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.

References

[1]

Adaricheva, K., Sloan, R. H., & Szörényi, B. (2012). Horn belief contraction: Remainders, envelopes and complexity. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, pp. 107-115.

Digital Library

[2]

Alchourrón, C. E., Gärdenfors, P., & Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. The Journal of Symbolic Logic, 50 (2), 510-530.

[3]

Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., & Patel-Schneider, P. F. (Eds.). (2003). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, New York, NY, USA.

Digital Library

[4]

Booth, R., Meyer, T., Varzinczak, I. J., & Wassermann, R. (2011). On the link between partial meet, kernel, and infra contraction and its application to Horn logic. Journal of Artificial Intelligence Research, 42, 31-53.

Digital Library

[5]

Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., & Rosati, R. (2007). Tractable reasoning and Efficient query answering in description logics: The DL-Lite family. Journal of Automatic Reasoning, 39 (3), 385-429.

Digital Library

[6]

Creignou, N., Papini, O., Pichler, R., & Woltran, S. (2014). Belief revision within fragments of propositional logic. Journal of Computer and System Sciences, 80 (2), 427-449.

Digital Library

[7]

Delgrande, J. P., & Jin, Y. (2012). Parallel belief revision: Revising by sets of formulas. Artificial Intelligence, 176 (1), 2223-2245.

Digital Library

[8]

Delgrande, J. P., & Peppas, P. (2015). Belief revision in Horn theories. Artificial Intelligence, 218, 1-22.

Digital Library

[9]

Delgrande, J. P., Peppas, P., & Woltran, S. (2018). General belief revision. Journal of the Association for Computing Machinery, 65 (5).

Digital Library

[10]

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

Digital Library

[11]

Fermé, E., Krevneris, M., & Reis, M. (2008). An axiomatic characterization of ensconcement-based contraction. Journal of Logic and Computation, 18 (5), 739-753.

Digital Library

[12]

Fuhrmann, A., & Hansson, S. O. (1994). A survey of multiple contractions. Journal of Logic, Language and Information, 3 (1), 39-74.

[13]

Gärdenfors, P. (1988). Knowledge in Flux: Modelling the Dynamics of Epistemic States. MIT Press.

[14]

Gärdenfors, P., & Makinson, D. (1988). Revisions of knowledge systems using epistemic entrenchment. In Proceedings of the 2nd conference on Theoretical Aspects of Reasoning about Knowledge, pp. 83-95.

Digital Library

[15]

Grove, A. (1988). Two modellings for theory change. Journal of Philosophical Logic, 17 (2), 157-170.

[16]

Hansson, S. O. (1991). Belief contraction without recovery. Studia Logica, 50 (2), 251-260.

[17]

Hansson, S. O. (1993). Changes of disjunctively closed bases. Journal of Logic, Language and Information, 2 (4), 255-284.

[18]

Hansson, S. O. (1999). A Textbook of Belief Dynamics: Theory Change and Database Updating. Kluwer.

[19]

Harper, W. L. (1976). Rational conceptual change. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, 1976, 462-494.

[20]

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

Digital Library

[21]

Kautz, H., & Selman, B. (1996). Knowledge compilation and theory approximation. Journal of the ACM, 43, 193-224.

Digital Library

[22]

Langlois, M., Sloan, R. H., Szörényi, B., & Turán, G. (2008). Horn complements: Towards Horn-to-Horn belief revision. In Proceedings of the 23rd National Conference on Artificial Intelligence, pp. 466-471.

Digital Library

[23]

Levi, I. (1991). The Fixation of Beliefs and its Undoing. Cambridge University Press.

[24]

Lewis, D. (1973). Counterfactuals. Harvard University Press.

[25]

Makinson, D. (1987). On the status of the postulate of recovery in the logic of theory change. Journal of Philosophical Logic, 16 (4), 383-394.

[26]

Peppas, P. (2008). Belief revision. In Handbook of Knowledge Representation, pp. 317-359. Elsevier Science.

[27]

Qi, G., & Du, J. (2009). Model-based revision operators for terminologies in description logics. In Proceedings of the 21st International Joint Conferences on Artificial Intelligence (IJCAI-2009), pp. 891-897.

Digital Library

[28]

Qi, G., Haase, P., Huang, Z., Ji, Q., Pan, J. Z., & Volker, J. (2008). A kernel revision operator for terminologies -- algorithms and evaluation. In Proceedings of the 7th International Semantic Web Conference (ISWC-2008), pp. 419-434.

Digital Library

[29]

Ribeiro, M. M., Wassermann, R., Flouris, G., & Antoniou, G. (2013). Minimal change: Relevance and recovery revisited. Artificial Intelligence, 201, 59-80.

Digital Library

[30]

Rott, H. (1991). Two methods of constructing contractions and revisions of knowledge systems. Journal of Philosophical Logic, 20 (2), 149-173.

[31]

Rott, H. (1992). Preferential belief change using generalised epistemic entrenchment. Journal of Logic, Language and Information, 1 (1), 45-78.

[32]

Rott, H., & Pagnucco, M. (1999). Severe withdrawal (and recovery). Journal of Philosophical Logic, 28 (5), 501-547.

[33]

Satoh, K. (1988). Nonmonotonic reasoning by minimal belief revision. In Proceedings of the International Conference on Fifth Generation Computer Systems, pp. 455-462.

[34]

Wang, Z., Wang, K., & Topor, R. W. (2015a). DL-Lite ontology revision based on an alternative semantic characterization. ACM Transactions on Computational Logic, 16 (4), 31:1-31:37.

Digital Library

[35]

Wang, Z., Wang, K., Zhuang, Z., & Qi, G. (2015b). Instance-driven ontology evolution in dl-lite. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 1656-1662.

Digital Library

[36]

Williams, M.-A. (1994). On the logic of theory base change. In Proceedings of the European Workshop on Logics in Artificial Intelligence, pp. 86-105.

Digital Library

[37]

Wu, M., Zhang, D., & Zhang, M. (2011). Language splitting and relevance-based belief change in horn logic. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, pp. 268-273.

Digital Library

[38]

Zhuang, Z., & Pagnucco, M. (2010). Horn contraction via epistemic entrenchment. In Proceedings of the 12th European Conference on Logics in Artificial Intelligence, pp. 339-351.

Digital Library

[39]

Zhuang, Z., & Pagnucco, M. (2011). Transitively Relational Partial Meet Horn Contraction. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 1132-1138.

Digital Library

[40]

Zhuang, Z., & Pagnucco, M. (2012). Model Based Horn Contraction. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, pp. 169-178.

Digital Library

[41]

Zhuang, Z., & Pagnucco, M. (2014). Entrenchment-based Horn contraction. Journal of Artificial Intelligence Research, 51, 227-254.

Digital Library

[42]

Zhuang, Z., Pagnucco, M., & Zhang, Y. (2013). Definability of Horn revision from Horn contraction. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pp. 1205-1211.

Digital Library

[43]

Zhuang, Z., Pagnucco, M., & Zhang, Y. (2017). Inter-definability of Horn contraction and Horn revision. Journal of Philosophical Logic, 46, 299-332.

[44]

Zhuang, Z., Wang, Z., Wang, K., & Qi, G. (2014). Contraction and revision over DL-Lite TBoxes. In Proceedings of the 28th AAAI Conference on Atificial Intelligence, pp. 1149-1156.

Digital Library

[45]

Zhuang, Z., Wang, Z., Wang, K., & Qi, G. (2016). DL-Lite contraction and revision. Journal of Artificial Intelligence Research, 56, 329-378.

Digital Library

Cited By

Bu W(2024)Data or mathematics? Solutions to semantic problems in artificial intelligenceJournal of Computational Methods in Sciences and Engineering10.3233/JCM-24752024:4-5(2847-2861)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.3233/JCM-247520
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

A generalisation of AGM contraction and revision to fragments of first-order logic
1. Theory of computation
  1. Models of computation

Recommendations

AGM Contraction and Revision of Rules

In this paper we study AGM contraction and revision of rules using input/output logical theories. We replace propositional formulas in the AGM framework of theory change by pairs of propositional formulas, representing the rule based character of ...
Belief revision within fragments of propositional logic

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given ...
AGM-Style Belief Revision of Logic Programs under Answer Set Semantics
LPNMR 2013: Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning - Volume 8148

In the past few years, several approaches for revision and update of logic programs have been studied. None of these however matched the generality and elegance of the original AGM approach to revision in classical logic. One particular obstacle is the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 64, Issue 1

January 2019

1007 pages

ISSN:1076-9757

Editor:
Satinder Singh

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 January 2019

Accepted: 01 January 2019

Received: 01 May 2018

Published in JAIR Volume 64, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bu W(2024)Data or mathematics? Solutions to semantic problems in artificial intelligenceJournal of Computational Methods in Sciences and Engineering10.3233/JCM-24752024:4-5(2847-2861)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.3233/JCM-247520
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

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents