Masterarbeit „Cyclic Rationality for AGM Revision in Propositional Logic“

Dr. Kai Sauerwald
in Bearbeitung


In knowledge representation, the field of belief change studies how the beliefs of an agent can change rationally (in the light of new information) [1]. A prominent theory is AGM theory, which is centred on the idea that belief changes should be minimal in the sense that agents should keep as possible of their initial beliefs. One of the primary operations considered by AGM theory is revision, which is the kind of belief change where a new belief is incorporated into the initial beliefs such that the new information is prioritized and inconsistencies are solved whenever that is possible. The axiomatization of AGM revision used today consists of postulates which are typically split into two groups, the basic postulates and the supplementary postulates. Some authors argue that the basic postulates already capture minimal change, and the supplementary postulates represent certain organizational principles regarding the interrelation of beliefs. Formally, Katsuno and Mendelzon [2] showed that AGM revision (with all postulates) is characterized by total preorders over the interpretations (when considering propositional logic). It is also known that replacing the supplementary postulates with other postulates leads to characterizations by different types of orderings than total preorders, e.g., semi-orders [3]. Today, for many types of orderings, a corresponding set of postulates C is unknown.

One open problem is supplementary postulates C, such that the basic AGM revision postulates + C is characterized by cyclic orders of the interpretations (when using propositional logic). Developing such a set of postulates C is a theoretical and challenging task that requires motivation, intuition and creativity. Typically, one defines candidates for C and then tries to verify that the postulates are sufficient and necessary for characterizing the goal. If the proofs fail, one constructs examples for the failure and adapts the postulates C carefully until a characterization is found.

The task of this thesis is to undertake an attempt to find such postulates C by performing these research steps as described above and documenting the process in their master's thesis. Finding such a set of postulates is not a criterium of success for this thesis. If requested, this thesis can be approached with intensive support from the supervisor (which is also advised).