Macquarie University
01whole.pdf (945.93 kB)

Belief Change without Compactness

Download (945.93 kB)
posted on 2022-11-15, 02:06 authored by Jandson Santos Ribeiro Santos

One of the main goals of Artificial Intelligence (AI) is to build rational agents that are capable of taking rational decisions autonomously. For this, it is essential to devise mechanisms to properly represent knowledge, and reason about the knowledge that an agent has about the world. However, an agent’s knowledge is not static - it gets updated as the agent acquires new information. One of the big challenges involving knowledge representation is how an agent ought to change its own knowledge and beliefs in response to any new information it acquires. This, in short, is the problem of belief change. Standard approaches of Belief Change come in two flavours: a set of rationality postulates that prescribes epistemic behaviours for an agent, and a collection of constructions, or functions, to perform such rational changes. The two foremost paradigms of Belief Change are the AGM paradigm (for belief change in a static environment) and the KM paradigm (for belief change in a dynamic environment). Both these paradigms make strong assumptions about the underlying logic used to express an agent beliefs, such as Supraclassicality and Compactness. Relying on these assumptions, however, is rather restrictive, since many logics that are important for both AI and Computer Science applications do not have them. This thesis focuses on extending Belief Change to the realm of non-compact logics. One of the side effects of dispensing with compactness is that standard constructions of both the AGM and the KM paradigms no longer nicely connect with the respective rationality postulates. In this work, I identify the reasons behind this breakdown. This in turn helps us identify some minimal conditions under which the existence of rational AGM and KM belief change operations is guaranteed. Subsequently we provide constructive accounts of AGM- and KM-rational belief change operations without the compactness assumption, and we offer full accounts of belief change for both the paradigms. The main difference of our approach from the standard ones relies on the way epistemic preference of an agent is represented: instead of remainders and Grove’s Systems of Spheres, we consider maximal complete theories and genuine partial relations over worlds. Furthermore, we also consider the connection between AGM revision and nonmonotonic reasoning (NMR) systems, often viewed to be two sides of the same coin. We demonstrate that the bridge between belief revision and NMR breaks down in the absence of compactness. We then identify the basis of this breakdown, and present a new non-monotonic system that appropriately connects with the AGM revision postulates even in absence of compactness. Significantly, this connection with the AGM paradigm is independent of any specific constructions (such as systems of spheres), and is directly established between the AGM postulates and the axioms of the proposed non-monotonic system.


Table of Contents

1 Introduction -- 2 Belief Systems and the AGM Paradigm -- 3 Dispensing with Compactness in the AGM Paradigm -- 4 KM Update in Non-Finitary Languages -- 5 AGM Belief Revision and Non-Monotonic Systems -- 6 Concluding Remarks -- A Proofs for the Introduction, and Chapter 3, Section 3.1 to 3.3 -- B Proofs for Chapter 3, Section 3.4 -- C Proofs for the Chapter 3, Section 3.5 -- D Proofs for Chapter 4 -- E Proofs for Chapter 5 -- Bibliography


A thesis submitted in fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computing Cotutelle thesis with the University of São Paulo (USP)

Awarding Institution

Macquarie University

Degree Type

Thesis PhD


Thesis (PhD), Department of Computing, Faculty of Science and Engineering, Macquarie University

Department, Centre or School

Department of Computing

Year of Award


Principal Supervisor

Abhaya Nayak

Additional Supervisor 1

Renata Wassermann


Copyright: The Author Copyright disclaimer:




200 pages

Usage metrics

    Macquarie University Theses


    Ref. manager