On the Size Complexity and Decidability of First-Order Progression

2026-05-15 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences, Robotics & Autonomous Systems · Depth: Expert, extended

Summary

This paper systematically analyzes the size complexity and decidability of first-order (FO) progression in the Situation Calculus, a formalism for reasoning about action and change. Progression, which updates a knowledge base to reflect action effects, generally requires second-order logic. The authors focus on three increasingly expressive classes of actions that admit FO progression: local-effect, normal, and acyclic actions. They demonstrate that under reasonable assumptions, the size of the FO progression for these action classes grows polynomially, or even linearly for local-effect and acyclic actions, while normal actions result in quadratic growth. Furthermore, the study shows that if the initial knowledge base belongs to decidable fragments like two-variable first-order logic ($\\textsc{FO}^{2}$) or universal theories with constants (UTC), the progression remains within these same fragments, thereby preserving decidability and practical applicability for query evaluation.

Key takeaway

For AI Scientists and Research Scientists developing intelligent agents in dynamic, open-world scenarios, understanding the computational properties of knowledge base progression is critical. Your choice of action theory (local-effect, normal, or acyclic) directly impacts the size complexity of the progressed knowledge base, with local-effect and acyclic actions offering linear growth and normal actions leading to quadratic growth. By ensuring your initial knowledge base adheres to decidable fragments like $\\textsc{FO}^{2}$ or UTC, you can guarantee that the progressed theory remains decidable, enabling efficient and effective query evaluation for tasks like planning and verification.

Key insights

First-order progression for specific action classes exhibits polynomial size growth and preserves decidability in restricted logical fragments.

Principles

• Progression is generally second-order, but specific action classes allow first-order definability.
• Size complexity is crucial for practical application of progression.
• Decidable logical fragments can be preserved through progression for effective query evaluation.

Method

The study uses the Situation Calculus framework, analyzing progression through forgetting predicates. It applies Ackermann's Lemma variants and iterative forgetting based on dependency graphs for different action classes.

In practice

• Use local-effect or acyclic actions for linear progression size.
• Ensure KBs are in $\\textsc{FO}^{2}$ or UTC for decidable progression.
• Prioritize progression over regression for repeated queries.

Topics

• First-Order Progression
• Situation Calculus
• Progression Size Complexity
• Progression Decidability
• Local-Effect Action Theories

Best for: AI Scientist, Research Scientist

Related on AIssential

• From Verdict to Process: Agentic Reinforcement Learning for Multi-Stage Fact Verification — End-to-end agentic reinforcement learning with process-aware rewards optimizes multi-stage fact verification for better performance and efficiency.
• Hierarchical Active Inference using Successor Representations — Hierarchical active inference with successor representations enables efficient, scalable planning in complex, dynamic environments.
• How Intelligence Emerges: A Minimal Theory of Dynamic Adaptive Coordination — Intelligence emerges from dynamic adaptive coordination in multi-agent systems via recursively closed feedback.
• The Math That Kills Trillion-Parameter AI Models — Knowledge graphs can serve as implicit reward models, enabling AI to learn logical deduction and generalize reasoning.
• Learning to Reason as Action Abstractions with Scalable Mid-Training RL — Mid-training with action abstractions optimizes LLM performance by minimizing RL and approximation errors.
• GAPD: Gold-Action Policy Distillation for Agentic Reinforcement Learning in Knowledge Base Question Answering — GAPD improves RL-based KBQA by adding dense token-level guidance via gold-action policy distillation and state alignment.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.