Walking the tightrope between expressiveness and uncomputability: AGM contraction beyond the finitary realm

Klumpp, Dominik and Santos Ribeiro Santos, Jandson 2024. Walking the tightrope between expressiveness and uncomputability: AGM contraction beyond the finitary realm. Presented at: The 22nd International Workshop on Nonmonotonic Reasoning (NMR 2024), Hanoi, Vietnam, 2-4 November 2024. Published in: Gierasimczuk, Nina and Heyninck, Jesse eds. Proceedings of the 22nd International Workshop on Nonmonotonic Reasoning (NMR 2024). , vol.3835 CEUR, pp. 34-43.

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

Although there has been significant interest in extending the AGM paradigm of belief change beyond finitary logics, the computational aspects of AGM have remained almost untouched. We investigate the computability of AGM contraction on non-finitary logics, and show an intriguing negative result: there are infinitely many uncomputable AGM contraction functions in such logics. Drastically, even if we restrict the theories used to represent epistemic states, in all non-trivial cases, the uncomputability remains. On the positive side, we use Büchi automata to construct computable AGM contraction functions on Linear Temporal Logic (LTL).

Item Type:	Conference or Workshop Item (Paper)
Status:	Published
Schools:	Schools > Computer Science & Informatics
Publisher:	CEUR
ISSN:	1613-0073
Date of First Compliant Deposit:	12 August 2025
Last Modified:	12 Aug 2025 09:43
URI:	https://orca.cardiff.ac.uk/id/eprint/180309

Actions (repository staff only)

Edit Item