Fragment-Driven Belief Change

Knowledge is continually evolving and obtained from different sources. Thus modifications, and likewise, combinations of knowledge bases are a central problem in many applications. In the area of Knowledge Representation & Reasoning (KRR), different forms of handling "knowledge in flux" have been proposed and accompanying methods and desiderata for operations like revision, update, contraction, and merge have been discussed. So far, the study of belief change was mainly devoted to "full" logic, i.e. the language is closed under standard logical connectives. Many applications however call for reasoning problems performed within a certain fragment of logic; in particular, the result of the performed change should remain in the fragment under consideration. This is motivated by two central observations. First, the language might be restricted a priori by an application. For instance, knowledge formalized as rules is much easier to handle for standard users. In case such users want to update their knowledge base, they indeed expect that the outcome is still in the easy-to-read format they are used to. Second, several fragments of propositional logic allow for efficient reasoning methods. Thus it is desirable that in case knowledge undergoes a change, the outcome remains in this tractable fragment. To summarize, we consider here scenarios where it is not only the knowledge base(s) and the new information which are given within a certain language fragment, but also the result of the change has to be located in the same fragment. Research in this particular direction has started only recently and so far focused on revision and contraction for the Horn fragment. However, several substantial scientific research questions in this context are still unresolved. The ultimate goal of this project is thus to understand the possibilities and limits of tailoring established belief change operators to fragments of propositional logic. In course of this project we want to fulfill the following achievements: A uniform formal approach for refining standard belief change operators with respect to several tractable fragments; formulations of properties such a refinement has to satisfy are required. Results about refined operators wrt. postulates. To this end, we require constructive characterization theorems for refined operators. Design of complexity-adequate algorithms for performing belief change operations; also an investigation of alternative (parameter-driven) algorithms is considered. Implementation of an easy-to-use prototype system for educational and scientific purposes which allows to experiment with different belief change operators in different fragments of logic. Application of the system to a particular domain where belief change in fragments of logic is implicitly required.

Knowledge is continually evolving and obtained from different sources. Thus, an understanding of how to modify and, likewise, combine different knowledge bases is an important prerequisite for many applications. In the area of Knowledge Representation and Reasoning, different forms of handling knowledge in flux, e.g., revision, update, contraction and merging have been proposed, and accompanying desiderata and methods for analyzing the above operations have been discussed. Significantly, until very recently the study of such change operations has been content with working in full logic, i.e., the language used to represent knowledge was assumed to be closed under standard logical connectives. However, many applications call for reasoning problems performed within a certain restricted fragment of logic. Consequently, the result of a performed change should remain in the fragment under consideration. This is motivated by two central observations.First, the language might be restricted a priori by an application. For instance, knowledge formalized as rules is much easier to handle for standard users; as an example consider a medical knowledge base that links certain symptoms and treatments via if-then-statements. In case such a knowledge base undergoes some update, the users indeed expect that the outcome is still in the easy-to-read format they are used to. Second, several fragments of propositional logic allow for efficient reasoning methods. Thus, it is desirable that in case knowledge undergoes a change, the outcome remains in this tractable fragment.To summarize, we consider here scenarios where it is not only the knowledge base(s) and the new information which are given within a certain language fragment, but also the result of the change has to be located in the same fragment. In the course of the project we obtained several results for this setting: (1) we have investigated to which extent the results delivered by standard operators may deviate from the target fragment, how to rectify such behavior and the limits (in terms of desired postulates) of such an approach; (2) as an alternative we followed the line of representation theorems that construct all possible operators satisfying the desired postulates when restricted to the fragment under consideration; (3) we studied the complexity of belief change in fragments and provided also a parameterized complexity analysis for standard belief revision operators; (4) we applied our methods to belief change operators for non-classical logics from the field of Artificial Intelligence, in particular to argumentation frameworks and logic programs; (5) finally we linked the concept of merging to voting operators. Since voting domains also can be seen as a restricted logical setting thus sharing some aspects with merging in fragments this provides an exciting avenue for future research in the field of social choice where our findings can play a crucial role.