Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Effective AGM Belief Contraction: A Journey beyond the Finitary Realm (Technical Report)

Created by
  • Haebom

Author

Dominik Klumpp, Jandson S. Ribeiro

Outline

This paper points out that despite significant efforts to extend the AGM belief-changing paradigm beyond finite logic, the computational aspects of AGMs have remained largely unexplored. We investigate the computability of AGM reductions in infinite logics and reveal an intriguing negative consequence: there exist infinitely many incomputable AGM reduction functions in these logics. More dramatically, we show that the current de facto standard computability control strategy, which relies on restricting the knowledge state space, fails, maintaining incomputability in all infinite cases. Given these devastating results, we propose a novel approach to controlling computability beyond finite domains. Using linear temporal logic (LTL) as a case study, we identify an infinite class of perfectly rational AGM reduction functions that are computable by design. We construct these functions using Büchi automata to represent and reason about LTL beliefs.

Takeaways, Limitations

Takeaways: By proving the incomputability of AGM reductions in infinite logic and exposing the limitations of existing computability control strategies, we offer a new direction for the study of belief change in infinite logic. We propose a computable AGM reduction function construction method based on Büchi automata using LTL, providing a practical solution for the study of belief change in infinite logic.
Limitations: This case study is limited to LTL. Generalization to other infinite logics requires further study. Further analysis is needed to determine the effectiveness and practical applicability of the proposed method.
👍