Belief change studies how to update knowledge bases used for reasoning. Traditionally belief revision has been based on full propositional logic. However, reasoning with full propositional knowledge bases is computationally hard, whereas reasoning with Horn knowledge bases is fast. In the past several years, there has been considerable work in belief revision theory on developing a theory of belief contraction for knowledge represented in Horn form. Our main focus here is the computational complexity of belief contraction, and, in particular, of various methods and approaches suggested in the literature.

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

Following the recent trend of adapting the AGM (Alchourron and Makinson 1985) framework to propositional Horn logic, Delgrande and Peppas (Delgrande and Peppas 2011) give a model theoretic account for revision in the Horn logic set- ting. The current paper complements their work by studying the model theoretic approach for contraction. A model based Horn contraction is constructed and shown to give a model theoretic account to the transitively relational partial meet Horn contraction studied in (Zhuang and Pagnucco 2011). Significantly however, in contrast to (Delgrande and Pep- pas 2011), our model-based characterisation of Horn contrac- tion does not require the property of Horn compliance and totality over preorders. The model based contraction, upon proper restriction, also gives a model theoretic account for the epistemic entrenchment based Horn contraction studied in (Zhuang and Pagnucco 2010a).

Belief change studies how to update knowledge bases used for reasoning. Traditionally belief revision has been based on full propositional logic. However, reasoning with full propositional knowledge bases is computationally hard, whereas reasoning with Horn knowledge bases is fast. In the past several years, there has been considerable work in belief revision theory on developing a theory of belief contraction for knowledge represented in Horn form. Our main focus here is the computational complexity of belief contraction, and, in particular, of various methods and approaches suggested in the literature. This is a natural and important question, especially in connection with one of the primary motivations for considering Horn representation: efficiency. The problems considered lead to questions about Horn envelopes (or Horn LUBs), introduced earlier in the context of knowledge compilation. This work gives a syntactic characterization of the remainders of a Horn belief set with respect to a consequence to be contracted, as the Horn envelopes of the belief set and an elementary conjunction corresponding to a truth assignment satisfying a certain explicitly given formula. This gives an efficient algorithm to generate all remainders, each represented by a truth assignment. On the negative side, examples are given of Horn belief sets and consequences where Horn formulas representing the result of contraction, based either on remainders or on weak remainders, must have exponential size for almost all possible choice functions (i.e., different possible choices of partial meet contraction). Therefore using the Horn framework for belief contraction does not by itself give us computational efficiency. Further work is required to explore the possibilities for efficient belief change methods.

Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on recent investigations by Delgrande on contraction for Horn logic. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. This result stands in contrast to Delgrandes conjecture that orderly maxichoice is the appropriate form of contraction for Horn logic. We then define a more appropriate notion of basic contraction for the Horn case, influenced by the convexity property holding for full propositional logic and which we refer to as infra contraction. The main contribution of this work is a result which shows that the construction method for Horn contraction for belief sets based on our infra remainder sets corresponds exactly to Hanssons classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through contraction for belief bases. We prove that kernel contraction for belief bases produces precisely the same results as the belief base version of infra contraction. The use of belief bases to obtain this result provides evidence for the conjecture that Horn belief change is best viewed as a 'hybrid' version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.

This paper presents a framework for relevance-based belief change in propositional Horn logic. We firstly establish a parallel interpolation theorem for Horn logic and show that Parikh's Finest Splitting Theorem holds with Horn formulae. By reformulating Parikh's relevance criterion in the setting of Horn belief change, we construct a relevance-based partial meet Horn contraction operator and provide a representation theorem for the operator. Interestingly, we find that this contraction operator can be fully characterised by Delgrande and Wassermann's postulates for partial meet Horn contraction as well as Parikh's relevance postulate without requiring any change on the postulates, which is qualitatively different from the case in classical propositional logic.

Following the recent trend of studying the theory of belief revision under the Horn fragment of propo- sitional logic this paper develops a fully charac- terised Horn contraction which is analogous to the traditional transitively relational partial meet contraction [Alchourron et al., 1985]. This Horn con- traction extends the partial meet Horn contraction studied in [Delgrande and Wassermann, 2010] so that it is guided by a transitive relation that models the ordering of plausibility over sets of beliefs.

A recent direction within belief revision theory is to develop a theory of belief change for the Horn knowledge representation framework. We consider questions related to the complexity aspects of previous work, leading to questions about Horn envelopes (or Horn LUB’s), introduced earlier in the context of knowledge compilation. A characterization is obtained of the remainders of a Horn be- lief set with respect to a consequence to be contracted, as the Horn envelopes of the belief set and an elementary conjunction corresponding to a truth assignment satisfying a certain body building formula. This gives an efficient algorithm to generate all remainders, each represented by a truth assignment. On the negative side, examples are given of Horn belief sets and consequences where Horn formulas representing the result of most contraction operators, based either on remainders or on weak remainders, must have exponential size.

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 expressive as full propositional logic. In this paper we consider approaches to belief contraction in Horn knowledge bases. We develop two broad approaches for Horn contraction, corresponding to the two major approaches in belief change, based on Horn belief sets and Horn belief bases. We argue that previous approaches, which have taken Horn remainder sets as a starting point, have undesirable properties, and moreover that not all desirable Horn contraction functions are captured by these approaches. This is shown in part by examining model-theoretic considerations involving Horn contraction. For Horn belief set contraction, we develop an account based in terms of weak remainder sets. Maxichoice and partial meet Horn contraction is specified, along with a consideration of package contraction. Following this we consider Horn belief base contraction, in which the underlying knowledge base is not necessarily closed under the Horn consequence relation. Again, approaches to maxichoice and partial meet belief set contraction are developed. In all cases, constructions of the specific operators and sets of postulates are provided, and representation results are obtained. As well, we show that problems arising with earlier work are resolved by these approaches.