On the Size Complexity and Decidability of First-Order Progression

Computer Science > Artificial Intelligence [Submitted on 12 May 2026] On the Size Complexity and Decidability of First-Order Progression Jens Classen, Daxin Liu Progression, the task of updating a knowledge base to reflect action effects, generally requires second-order logic. Identifying first-order special cases, by restricting either the knowledge base or action effects, has long been a central topic in reasoning about actions. It is known that local-effect, normal, and acyclic actions, three increasingly expressive classes, admit first-order progression. However, a systematic analysis of the size of such progressions, crucial for practical applications, has been missing. In this paper, using the framework of Situation Calculus, we show that under reasonable assumptions, first-order progression for these action classes grows only polynomially. Moreover, we show that when the KB belongs to decidable fragments such as two-variable first-order logic or universal theories with constants, the progression remains within the same fragment, ensuring decidability and practical applicability. Comments: This is an extended version of an identically-titled paper accepted for publication at IJCAI 2026. This version contains an appendix with further proofs Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.12691 [cs.AI]   (or arXiv:2605.12691v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.12691 Focus to learn more Submission history From: Jens Classen [view email] [v1] Tue, 12 May 2026 19:40:45 UTC (32 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)