The Challenges of Effective AGM Belief Contraction

Autor:	Klumpp, Dominik, Ribeiro, Jandson S.
Rok vydání:	2024
Předmět:	Computer Science - Logic in Computer Science Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	Despite the 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 identify an infinite class of computable AGM contraction functions on Linear Temporal Logic (LTL). We use B\"uchi automata to construct such functions as well as to represent and reason about LTL knowledge. Comment: 20 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2409.09171 Zobrazit plný text záznamu View this record from Arxiv