人工知能におけるアクション推論（reasoning about actions）の中心的なタスクの一つに進行（progression）がある。これは、アクションの効果を反映するために知識ベースを更新する作業である。進行は一般に二階論理を必要とするため、計算上の課題が生じる。しかし、知識ベースやアクション効果に制限を課すことで、一階論理で表現可能な特殊ケースが長年研究されてきた。局所効果（local-effect）、正規（normal）、非循環（acyclic）の各アクションクラスは、表現力が増大する順に一階進行を許容することが知られているが、その進行のサイズ複雑性については体系的な分析が欠けていた。
IJCAI 2026で発表された論文「On the Size Complexity and Decidability of First-Order Progression」において、著者のJens Classen氏とDaxin Liu氏は、状況計算（Situation Calculus）の枠組みを用いてこの問題に取り組んだ。彼らは、合理的な仮定の下で、上記3つのアクションクラスに対する一階進行のサイズが多項式的にしか増大しないことを証明した。これは指数関数的な爆発を回避できることを意味し、実用上極めて重要である。
さらに、本論文は決定可能性の問題も扱う。知識ベースが二変数一階論理（two-variable first-order logic）や定数付き全称理論（universal theories with constants）などの決定可能な断片に属する場合、進行後の知識ベースも同じ断片にとどまることを示した。これにより、進行後も推論が決定可能であることが保証される。
この研究は、進行理論の未解決問題を解決し、効率的な進行アルゴリズムの設計と実装に理論的基盤を提供する。論文にはさらなる証明を含む付録も付されており、今後の研究の足掛かりとなる。自動計画やロボット制御など、アクション推論を必要とする応用分野への貢献が期待される。