article

Horn clause contraction functions

Authors:

James P. Delgrande,

Renata WassermannAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 48, Issue 1

Pages 475 - 511

Published: 01 October 2013 Publication History

Abstract

In classical, AGM-style belief change, it is assumed that the underlying logic contains classical propositional logic. This is clearly a limiting assumption, particularly in Artificial Intelligence. Consequently there has been recent interest in studying belief change in approaches where the full expressivity of classical propositional logic is not obtained. In this paper we investigate belief contraction in Horn knowledge bases. We point out that the obvious extension to the Horn case, involving Horn remainder sets as a starting point, is problematic. Not only do Horn remainder sets have undesirable properties, but also some desirable Horn contraction functions are not captured by this approach. For Horn belief set contraction, we develop an account in terms of a model-theoretic characterisation involving weak remainder sets. Maxichoice and partial meet Horn contraction is specified, and we show that the problems arising with earlier work are resolved by these approaches. As well, constructions of the specific operators and sets of postulates are provided, and representation results are obtained. We also examine Horn package contraction, or contraction by a set of formulas. Again, we give a construction and postulate set, linking them via a representation result. Last, we investigate the closely-related notion of forgetting in Horn clauses. This work is arguably interesting since Horn clauses have found widespread use in AI; as well, the results given here may potentially be extended to other areas which make use of Horn-like reasoning, such as logic programming, rule-based systems, and description logics. Finally, since Horn reasoning is weaker than classical reasoning, this work sheds light on the foundations of belief change.

References

[1]

Alchourron, C. E., ' Makinson, D. (1985). On the logic of theory change: Safe contraction. Studia Logica, 44 (4), 405-422.

[2]

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

[3]

Anderson, A., ' Belnap Jr., N. (1975). Entailment: The Logic of Relevance and Necessity, Vol. I. Princeton University Press.

[4]

Baader, F., Calvanese, D., McGuiness, D., Nardi, D., ' Patel-Schneider, P. (Eds.). (2007). The Description Logic Handbook (second edition). Cambridge University Press.

[5]

Booth, R., Meyer, T., Varzinczak, I., '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

[6]

Booth, R., Meyer, T., ' Varzinczak, I. (2009). Next steps in propositional Horn contraction. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 702-707, Pasadena, CA.

[7]

Creignou, N., Papini, O., Pichler, R., ' Woltran, S. (2012). Belief revision within fragments of propositional logic. In Brewka, G., Eiter, T., ' McIlraith, S. A. (Eds.), Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning. AAAI Press.

[8]

Delgrande, J., ' Wassermann, R. (2010). Horn clause contraction functions: Belief set and belief base approaches. In Lin, F., ' Sattler, U. (Eds.), Proceedings of the Twelfth International Conference on the Principles of Knowledge Representation and Reasoning, pp. 143-152, Toronto. AAAI Press.

[9]

Delgrande, J. (2008). Horn clause belief change: Contraction functions. In Brewka, G., ' Lang, J. (Eds.), Proceedings of the Eleventh International Conference on the Principles of Knowledge Representation and Reasoning, pp. 156-165, Sydney, Australia. AAAI Press.

[10]

Delgrande, J., ' Peppas, P. (2011). Revising Horn Theories. In Twenty-Second International Joint Conference on Artificial Intelligence, pp. 839-844.

[11]

Delgrande, J., ' Wassermann, R. (2011). Topics in Horn contraction: Supplementary postulates, package contraction, and forgetting. In IJCAI-11 Workshop on Nonmonotonic Reasoning, Action and Change (NRAC-11), pp. 87-94, Barcelona, Spain.

[12]

Eiter, T., ' Gottlob, G. (1992). On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, 57 (2-3), 227-270.

Digital Library

[13]

Flouris, G., Plexousakis, D., ' Antoniou, G. (2004). Generalizing the AGM postulates: Preliminary results and applications. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR-04), pp. 171-179, Whistler BC, Canada.

[14]

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

[15]

Gärdenfors, P., ' Makinson, D. (1988). Revisions of knowledge systems using epistemic entrenchment. In Proc. Second Theoretical Aspects of Reasoning About Knowledge Conference, pp. 83-95, Monterey, Ca.

[16]

Garey, M., ' Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York.

[17]

Grove, A. (1988). Two Modellings for Theory Change. Journal of Philosophical Logic, 17, 157-170.

[18]

Hansson, S. O. (1999). A Textbook of Belief Dynamics. Applied Logic Series. Kluwer Academic Publishers.

[19]

Khardon, R. (1995). Translating between Horn representations and their characteristic models. Journal of Artificial Intelligence Research, 3, 349-372.

Digital Library

[20]

Lakemeyer, G., ' Levesque, H. (2000). The Logic of Knowledge Bases. MIT Press, Cambridge, MA.

[21]

Lang, J., ' Marquis, P. (2002). Resolving inconsistencies by variable forgetting. In Proceedings of the Eighth International Conference on the Principles of Knowledge Representation and Reasoning, pp. 239-250, San Francisco. Morgan Kaufmann.

[22]

Langlois, M., Sloan, R., Szörényi, B., ' Turán, G. (2008). Horn complements: Towards Horn-to-Horn belief revision. In Proceedings of the AAAI National Conference on Artificial Intelligence, Chicago, Il.

[23]

Liberatore, P. (2000). Compilability and compact representations of revision of Horn knowledge bases. ACM Transactions on Computational Logic, 1 (1), 131-161.

Digital Library

[24]

Lin, F., ' Reiter, R. (1994). Forget it!. In AAAI Fall Symposium on Relevance, New Orleans.

[25]

Makinson, D. (2009) Personal communication.

[26]

Peppas, P. (2008). Belief revision. In van Harmelen, F., Lifschitz, V., ' Porter, B. (Eds.), Handbook of Knowledge Representation, pp. 317-359. Elsevier Science, San Diego, USA.

[27]

Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32 (1), 57-96.

Digital Library

[28]

Rott, H. (1992). On the logic of theory change: More maps between different kinds of contraction functions. In Gärdenfors, P. (Ed.), Belief Revision, No. 29 in Cambridge Tracts in Theoretical Computer Science, pp. 122-141. Cambridge University Press.

[29]

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

Digital Library

[30]

Zhuang, Z., ' Pagnucco, M. (2010a). Horn contraction via epistemic entrenchment. In Janhunen, T., ' Niemelä, I. (Eds.), Logics in Artificial Intelligence - 12th European Conference (JELIA 2010), Vol. 6341 of Lecture Notes in Artificial Intelligence, pp. 339-351. Springer Verlag.

[31]

Zhuang, Z., ' Pagnucco, M. (2010b). Two methods for constructing Horn contractions. In Li, J. (Ed.), AI 2010: Advances in Artificial Intelligence - 23rd Australasian Joint Conference, Vol. 6464 of Lecture Notes in Artificial Intelligence, pp. 72-81. Springer Verlag.

[32]

Zhuang, Z. (2012). Belief Change Under the Horn Fragment of Propositional Logic. Ph. D. thesis, School of Computer Science and Engineering - University of New South Wales.

[33]

Zhuang, Z., ' Pagnucco, M. (2011). Transitively relational partial meet Horn contraction. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pp. 1132-1138, Barcelona, Spain.

[34]

Zhuang, Z., ' Pagnucco, M. (2012). Model based Horn contraction. In Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning, Rome, Italy.

Cited By

Zhuang ZWang ZWang KDelgrande J(2019)A generalisation of AGM contraction and revision to fragments of first-order logicJournal of Artificial Intelligence Research10.1613/jair.1.1133764:1(147-179)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11337
Creignou NHaret APapini OWoltran S(2018)Belief update in the horn fragmentProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304906(1781-1787)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304906
Delgrande JPeppas PWoltran S(2018)General Belief RevisionJournal of the ACM10.1145/320340965:5(1-34)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3203409
Show More Cited By

Horn clause contraction functions
1. Theory of computation

Recommendations

Horn clause contraction functions: belief set and belief base approaches
KR'10: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning

Standard approachs to belief change assume that the underlying logic contains classical propositional logic. Recently there has been interest in investigating approaches to belief change, specifically contraction, in which the underlying logic is not as ...
Entrenchment-based Horn contraction

The AGM framework is the benchmark approach in belief change. Since the framework assumes an underlying logic containing classical Propositional Logic, it can not be applied to systems with a logic weaker than Propositional Logic. To remedy this ...
Horn clause belief change: contraction functions
KR'08: Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning

The standard (AGM) approach to belief change assumes that the underlying logic is at least as strong as classical propositional logic. This paper investigates an account of belief change, specifically contraction, where the underlying logic is that ...

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 48, Issue 1

October 2013

990 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 October 2013

Published in JAIR Volume 48, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
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

Zhuang ZWang ZWang KDelgrande J(2019)A generalisation of AGM contraction and revision to fragments of first-order logicJournal of Artificial Intelligence Research10.1613/jair.1.1133764:1(147-179)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11337
Creignou NHaret APapini OWoltran S(2018)Belief update in the horn fragmentProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304906(1781-1787)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304906
Delgrande JPeppas PWoltran S(2018)General Belief RevisionJournal of the ACM10.1145/320340965:5(1-34)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3203409
Delgrande J(2017)A knowledge level account of forgettingJournal of Artificial Intelligence Research10.5555/3207692.320771860:1(1165-1213)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.5555/3207692.3207718
Haret ARümmele SWoltran S(2017)Merging in the Horn FragmentACM Transactions on Computational Logic10.1145/304370018:1(1-32)Online publication date: 16-Mar-2017
https://dl.acm.org/doi/10.1145/3043700
Creignou NKtari RPapini O(2016)Belief contraction within fragments of propositional logicProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-390(390-398)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-390
Creignou NPapini ORümmele SWoltran S(2016)Belief Merging within Fragments of Propositional LogicACM Transactions on Computational Logic10.1145/289843617:3(1-28)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2898436
Santos YRibeiro MWassermann R(2015)Between belief bases and belief setsProceedings of the 2015 International Conference on Defeasible and Ampliative Reasoning - Volume 142310.5555/2907094.2907103(50-56)Online publication date: 27-Jul-2015
https://dl.acm.org/doi/10.5555/2907094.2907103
Zhuang ZWang ZWang KDelgrande J(2015)Extending AGM contraction to arbitrary logicsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832709(3299-3305)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832709
Haret ARümmele SWoltran S(2015)Merging in the horn fragmentProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832673(3041-3047)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832673
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents