Fragments of propositional logic, i.e., tailored sub-languages designed for neatly structured data, are relevant in many practical settings. This paper studies belief update in fragments (e.g., Horn, Krom, affine) that obey a desirable semantic closure condition. We assume update is guided by the well-known Katsuno-Mendelzon (KM) postulates, which in full propositional logic characterize update operators as choice functions guided by total or partial preorders over possible worlds. Because many useful fragments cannot express every connective (e.g., they often lack closure under disjunction), the KM axioms must be rephrased and supplemented to keep updates rational in these less expressive environments. Our main result is a set of representation theorems: once the KM postulates are adjusted, they capture exactly the update operators generated by suitably constrained total or partial preorders within the fragment. In addition, we clarify how revision works in fragments when partial preorders are allowed and also present concrete, fragment-friendly update operators.

Belief change is an important topic of knowledge representation and reasoning in artificial intelligence. Within the logical framework, the AGM approach has become a standard and various belief change operations have been considered. While revision, contraction and updating have given rise to a great deal of work, erasure has so far attracted less interest. Erasure is to contraction what update is to revision.This article deals with the study of erasure within the framework of propositional logic. It extends Katsuno and Mendelzon’s approach with additional postulates capturing the minimality of change and proposes two representation theorems for erasure operators, one in terms of total preorders on interpretations, the other in terms of partial preorders on interpretations. Finally, it completes the work of Caridroit, Konieczny and Marquis for contraction by proposing a new representation theorem for contraction operators in terms of partial preorders on interpretations.

Abstract Recently, belief change within the framework of fragments of propositional logic has gained attention. In the context of revision, it has been proposed to refine existing operators so that they operate within propositional fragments and that the result of revision remains in the fragment under consideration. Later, this notion of refinement was generalized to belief change operators. Whereas refinement allowed one to define concrete rational operators adapted to propositional fragments in the context of revision and update, it has to be specified for contraction and erasure. We propose a specific notion of refinement for contraction and erasure operators, called reasonable refinement. This allows us to provide refined contraction and erasure operators that satisfy the basic postulates. We study the logical properties of reasonable refinement of two model-based contraction operators and two model-based erasure operators. Our approach is not limited to the Horn fragment but applicable to many fragments of propositional logic, like Krom and affine fragments.

The paper deals with base revision for Answer Set Programming (ASP). Base revision in classical logic is done by the removal of formulas. Exploiting the non-monotonicity of ASP allows one to propose other revision strategies, namely addition strategy or removal and/or addition strategy. These strategies allow one to define families of rule-based revision operators. The paper presents a semantic characterization of these families of revision operators in terms of answer sets. This semantic characterization allows for equivalently considering the evolution of syntactic logic programs and the evolution of their semantic content. It then studies the logical properties of the proposed operators and gives complexity results.

In line with recent work on belief change in fragments of propositional logic, we study belief update in the Horn fragment. We start from the standard KM postulates used to axiomatize belief update operators; these postulates lend themselves to semantic characterizations in terms of partial (resp. total) preorders on possible worlds. Since the Horn fragment is not closed under disjunction, the standard postulates have to be adapted for the Horn fragment. Moreover, a restriction on the preorders (i.e., Horn compliance) and additional postulates are needed to obtain sensible characterizations for the Horn fragment, and this leads to our main contribution: a representation result which shows that the class of update operators captured by Horn compliant partial (resp. total) preorders over possible worlds is precisely that given by the adapted and augmented Horn update postulates. With these results at hand, we provide concrete Horn update operators and are able to shed light on Horn revision operators based on partial preorders.

Belief base revision has been studied within the answer set programming framework. We go a step further by introducing uncertainty and studying belief base revision when beliefs are represented by possibilistic logic programs under possibilistic answer set semantics and revised by certain input. The paper proposes two approaches of rule-based revision operators and presents their semantic characterization in terms of possibilistic distribution. This semantic characterization allows for equivalently considering the evolution of syntactic logic programs and the evolution of their semantic content. It then studies the logical properties of the proposed operators and gives complexity results.

Belief change within the framework of fragments of propositional logic is one of the main and recent challenges in the knowledge representation research area. While previous research works focused on belief revision, belief merging, and belief contraction, the problem of belief update within fragments of classical logic has not been addressed so far. In the context of revision, it has been proposed to refine existing operators so that they operate within propositional fragments, and that the result of revision remains in the fragment under consideration. This approach is not restricted to the Horn fragment but also applicable to other propositional fragments like Krom and affine fragments. We generalize this notion of refinement to any belief change operator. We then focus on a specific belief change operation, namely belief update. We investigate the behavior of the refined update operators with respect to satisfaction of the KM postulates and highlight differences between revision and update in this context.

Recently, belief change within the framework of fragments of propositional logic has gained attention. In the context of revision it has been proposed to refine existing operators so that they operate within propositional fragments, and that the result of revision remains in the fragment under consideration. In this paper we generalize this notion of refinement to belief change operators. Whereas the notion of refinement allowed one to define concrete rational operators adapted to propositional fragments in the context of revision and update, it has to be specified for contraction. We propose a specific notion of refinement for contraction operators, called reasonable refinement. This allows us to provide refined contraction operators that satisfy the basic postulates for contraction. We study the logical properties of reasonable refinements of two well-known model-based contraction operators. Our approach is not limited to the Horn fragment but applicable to many fragments of propositional logic, like Horn, Krom and affine fragments.

Recently, belief change within the framework of fragments of propositional logic has gained increasing attention. Previous research focused on belief contraction and belief revision on the Horn fragment. However, the problem of belief merging within fragments of propositional logic has been mostly neglected so far. We present a general approach to defining new merging operators derived from existing ones such that the result of merging remains in the fragment under consideration. Our approach is not limited to the case of Horn fragment; it is applicable to any fragment of propositional logic characterized by a closure property on the sets of models of its formulæ. We study the logical properties of the proposed operators regarding satisfaction of merging postulates, considering, in particular, distance-based merging operators for Horn and Krom fragments.

The paper proposes an extension of “Prioritized Removed Sets Revision” (PRSR) to DL-LiteRstratified knowledge bases. The revision strategy is based on inconsistency minimization and consists in determining smallest subsets of assertions to be dropped from the current DL-LiteRknowledge base, taking the stratification into account, in order to restore consistency and accept the input. We consider different forms of input: membership assertion, positive inclusion axiom or negative inclusion axiom. We show that according to the form of input and under some conditions PRSR can be achieved in polynomial time.

Artificial intelligence (AI) was not born ex nihilo in the mid-fifties of the XXthcentury. Beyond its immediate roots in cybernetics and in computer science that started about two decades before, its emergence is the result of a long and slow process in the history of humanity. This can be articulated around two main questions: the formalization of reasoning and the design of machines having autonomous capabilities in terms of computation and action. The aim of this paper is to gather some insufficiently known elements about the prehistory of AI in the last 350 years that precede the official birth of AI, a time period where only a few very well-known names, such as Thomas Bayes and Georges Boole, are usually mentioned in relation with AI.

Merging multiple sources of information is a rising subject in artificial intelligence. Most of the proposals are model-based approaches with very high computational complexity, moreover few experimentations are available. This paper proposes a framework for performing Removed Sets Fusion (RSF) of belief bases consisting of prepositional formulae. It then describes the implementation of RSF which stems from Answer Set Programming (ASP) and can be performed with any ASP solver supporting the minimize statement. It finally presents an experimental study and a comparison.

This paper deals with iterated belief change. Epistemic states are suitable to represent an intelligent agent's knowledge. Most of the time, when dealing with geographic information, the agent faces incomplete, uncertain, or inaccurate information and needs a mechanism for either revision, update, or fusion to handle their change in beliefs in the presence of new items of information. After some preliminaries on the representation of epistemic states by means of pre-orders, the paper presents three approaches to belief change: revision, update, and fusion. For each of these approaches, the background, postulates, representation by pre-orders, and semantic and syntactic requirements are given. In each case, the approaches are illustrated by examples.