EPS
← All batches·2605.12691

On the Size Complexity and Decidability of First-Order Progression

topic: current_projecttop score: 86released: 2026-05-15first surfaced: 2026-05-14arXivPDFlinked_to_results2026-05-142026-05-15

Authors: Jens Classen, Daxin Liu

arXiv · PDF

Summary

arXiv:2605. 12691v1 Announce Type: new Abstract: Progression, the task of updating a knowledge base to reflect action effects, generally requires second-order logic.

Relevance

Read next because On the Size Complexity and Decidability of First-Order Progression overlaps with clean result "Leakage rate is a usable signal for recovering trigger-shaped phrases on Gaperon-1125-1B without knowing the hidden trigger itself (MODERATE confidence)", clean result "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)", clean result "A pretraining-data-poisoned Qwen3-4B backdoor only fires on the exact trigger tokens — paraphrases don't activate it, and base-model similarity to the trigger doesn't predict which inputs fire (MODERATE confidence)". Matching terms: class, under. Source: arxiv cs.AI (Artificial Intelligence).

Abstract

arXiv:2605.12691v1 Announce Type: new Abstract: 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.