Many reasoning problems in AI are naturally stated in second-order logic, which can quantify over whole predicates ("there exists a relation P such that…"). Two examples are circumscription, which says "assume as few abnormal things as possible," and progression of an agent's knowledge after an action. Solvers cannot run such statements directly. The standard fix is second-order quantifier elimination: a rewriting procedure, driven by Ackermann's Lemma, that finds a first-order formula $A$ bounding the predicate from below and substitutes $A$ for every occurrence of the predicate. This works, but it has two practical problems. Substitution can make the output exponentially larger. It is also monolithic: when a new rule arrives, the lower bound changes from $A$ to $A \lor B$, the old substituted formula is no longer valid, and the whole elimination has to be rerun.
This note proposes a different output format. The eliminated predicate is not substituted away. It survives as a fresh symbol carrying its own definition, $\forall x\,(P'(x) \leftrightarrow A(x))$, which is a Clark-completion-style axiom, alongside the untouched context $H(P')$. Adding a rule then edits one definition instead of the whole theory. Iterated progression becomes a growing chain of small definitions instead of a nested substitution. When the bound $A$ mentions $P$ itself (recursion), the definition becomes a least-fixpoint (inductive) definition. A conflict-driven answer-set solver can check such definitions lazily, rather than requiring every loop formula up front. The deliverable is a theory of which updates this format keeps local, together with a working pipeline measured on the classical action domains.
Core Claim
Ackermann's Lemma states $\exists P\,\forall x\,[(A(x)\to P(x)) \land H(\neg P)] \equiv H(A)$, where $H$ is negative in $P$. The right-hand side is equivalent, modulo a fresh symbol $P'$, to the definitional extension $\forall x(P'(x)\leftrightarrow A(x)) \land H(P')$. This is the same move Tseitin-style naming makes in clause-form conversion. The idea is simple, and its value lies in three consequences that we claim can be proved and measured.
The first consequence concerns size. Iterated first-order progression kept in definitional form grows at most linearly in the number of actions and the size of the action theory. This contrasts with the $O(2^{mn})$ bound that Liu & Lakemeyer prove for substituted progression of general local-effect knowledge bases.
The second consequence is a locality result. We conjecture that an update is local in this format exactly when it does one of two things: it adds a new lower-bound clause $B \to P$, which the pipeline absorbs by extending one definition to $A \lor B$, or it adds a constraint in which eliminated predicates occur only negatively, which the pipeline absorbs by appending it. Any update that uses an eliminated predicate as a gate on the derivation of another minimized predicate forces that predicate's definition to be recomputed. Our hypothesis is that, specialized to default theories, this boundary coincides with Imielinski's Theorem 7, which says only prerequisite-free seminormal defaults translate modularly into circumscription. Imielinski's result therefore acts as a constraint on the design, not a contradiction of it. We do not claim to escape the theorem. We claim to find where it bites inside elimination pipelines and to make everything on the safe side of that line cheap.
The third consequence concerns recursion. When $A$ is recursive, the definition is inductive. Under circumscription the minimal models then coincide with the models of the completion plus loop formulas, by the propositional result of Lee & Lin. Those loop formulas need not be generated statically. They can be learned on demand as unfounded-set nogoods, as clasp does (Gebser et al.). This yields a partial, execution-level answer to the first-order loop-formula problem that Lee and Lin leave open. The definitions stay first-order and unground; loop checking happens only over the finite portion a query touches.
Research Program
The first component is a modified elimination algorithm, which we call definitional DLS. Doherty, Łukaszewicz and Szałas give a four-phase pipeline: preprocess, prepare the Ackermann form, substitute, then simplify and unskolemize. We keep their first two phases unchanged. In phase three we emit a named definition instead of substituting. Phase four is restricted to Skolem symbols internal to a single definition. As a result, the unskolemization failures the file describes, and the manual unskolemization that Kartha & Lifschitz needed after SCAN, stay contained to one definition rather than contaminating the whole output. We will prove equivalence modulo the fresh symbols. We will also prove that the output never exceeds the input plus one definition per eliminated occurrence group.
The second component is the modularity theory. We will define an update operator on definitional outputs, prove that the two local update classes above preserve equivalence with rerunning elimination from scratch, and give a dependency-graph criterion for when non-local updates can be confined to the strongly connected component of the affected predicate. This is analogous to how Lin & Zhao localize tightness repairs to strongly connected components. The theory also connects to Progression of Decomposed Situation Calculus Theories, which shows that modules stay separable only when the shared vocabulary contains no fluents. Our named definitions give a place to put shared fluents: a fluent can be exported as a defined symbol whose definition sits in one module. We will test whether this recovers local progression for some global-effect domains that paper excludes.
The third component is iterated progression. Progression following Liu and Lakemeyer is forgetting old fluent values and then asserting new effects, and each step becomes a definitional elimination. We will compare this against Liu & Claßen's PANACK and disjunctive-normal classes, which guarantee iterability through syntactic closure but have no implementation and no runtime data. Definitional form achieves iterability trivially, because each step's output is again definitions plus context. The price is a growing auxiliary vocabulary. The open question we will study is when chains of definitions can be collapsed back into PANACK form, which would bound that growth.
The fourth component is the backend split. Non-recursive definitions stay in classical first-order logic and go to a first-order prover or SMT solver. This preserves the decidability that Zhang & Ying establish for circumscription over fragments such as Bernays–Schönfinkel, which stable-model semantics loses. Only recursive definitions are routed to an answer-set solver with lazy unfounded-set checking. This directly addresses the tension that T2LP and F2LP push all of circumscription through stable models.
Baselines
The naive reference point is full re-elimination: rerunning our own DLS implementation from scratch, with substitution, after every update or action. It uses the same code, machine, and time limits, so any speedup we report is attributable to the definitional format and incremental updates alone. Beating it means matching its answers exactly while reducing per-update latency by a margin that grows with knowledge-base size. If the gap stays constant, the format adds nothing.
The strongest existing system is the grounding route of Lee & Palla. It translates situation-calculus theories through F2LP into answer-set programs with a bounded horizon, solves them with a clasp-family solver, and re-translates after each domain change. It is the strongest competitor because clasp is very fast on ground programs. The file reports clasp beating smodels by multiple orders of magnitude on non-tight programs, but gives no per-instance numbers, so there is no reported result on Lacuna for clasp's absolute runtimes. We will run it at the horizon our queries need, with the same solver version that serves our recursive backend. Beating it means lower total time across an action sequence of length $k$ once $k$ exceeds some crossover, plus correct answers at horizons where grounding runs out of memory.
For symbolic first-order-to-logic-program translation, T2LP is the reference. On 2-Clique Coloring, T2LP with the CLASPD backend solved 100-vertex instances in about 80 seconds, while DLV timed out beyond one hour at 40 vertices. We will rerun T2LP on the same instances and hardware and add a stream of rule updates. Because T2LP is non-modular, it re-translates after each update.
The historical elimination reference is SCAN on Blocks World: 14 clauses in 1.6 seconds on a Sun 4, reported by Kartha & Lifschitz. This figure is not comparable in wall-clock terms. We will reproduce the clause output as a correctness check.
Two ablations isolate the key ingredients. The first keeps definitional output but disables incremental updates, which separates the size benefit from the locality benefit. The second replaces lazy loop nogoods with static loop formulas in the style of Lee's translations, which tests whether on-demand learning matters on cyclic causal theories.
Why not just…?
Why not just use regression? Regression avoids second-order logic entirely, and for short action histories it is likely to beat us. Liu and Lakemeyer note that regressed queries grow with history length, but the file gives no measured crossover. We will include regression as an additional baseline over action sequences of increasing length and report where, if anywhere, it overtakes our method. If regression wins at every tested length, the progression half of the proposal is not worth pursuing.
Why not just ground and solve with clasp? This is the real threat. On bounded, fully known domains, grounding plus conflict-driven solving may simply be faster. The grounded pipeline of Lee and Palla requires a fixed horizon and suffers memory blowup on deep horizons, and DLV grounding already failed at 40 vertices in the T2LP experiments. Those failures motivate our approach but do not settle the comparison, which is exactly what the horizon-scaling experiment below measures. We keep clasp inside our system for the recursive definitions. The claim is not that grounding is bad. The claim is that grounding should apply only to the recursive core.
Why not just use Clark's completion? For stratified, acyclic theories, completion is exactly what our non-recursive definitions reduce to, as Lin shows for the causal predicate $Caused$. We claim no gain there. Completion admits self-supporting models on cyclic theories, as seen with recursive reachability in Robby's Apartment and with mutual causal ramifications. Our recursive-definition path exists for exactly those cases. The ablation with loop checking disabled will count the spurious models that plain completion would accept.
Isn't this just Tseitin-style naming? Mechanically, yes. What is new is the locality characterization, its match or mismatch with Imielinski's boundary, and the claim that naming turns the iterability problem into bookkeeping. If the characterization turns out to be trivial, or the auxiliary vocabulary grows fast enough to cancel the size savings, the contribution shrinks to an engineering note. The size experiment will reveal this.
Proposed Experiments
We will use the domains in the file: Blocks World with painting, Murder Mystery, Suitcase, Robby's Apartment (recursive), Exploding Bomb and Box (global effects, cyclic fluents, from Liu & Claßen), and Stacks World (decomposition). Beyond the cited toy sizes, we will generate parameterized families that scale the number of objects, fluents, and actions. Ground-truth answers come from the grounded baseline at small sizes. We add 2-Clique Coloring and QBF from T2LP, extended with random rule-insertion streams. We also use the Hamiltonian Circuit random graphs. On nv60a540, Lin and Zhao's tight encoding cut ASSAT runtime from 3664.8 to 5.6 seconds, but on hand-coded 2xp and 4xp instances it lost to the original encoding, which makes these graphs a natural test of whether our cycle-scoped updates avoid auxiliary-atom damage.
Metrics are per-update latency, output size in symbols over $k$ progression steps, query-answering time, peak memory, and exact agreement of answers with ground truth.
Three decisive checks follow. First, output size under definitional progression should grow linearly in $k$ on Exploding Bomb and Box, while substituted re-elimination grows superlinearly. If both grow alike, the size claim is false. Second, on insertion streams restricted to the conjectured local class, incremental update must agree with full re-elimination on every instance. We will also construct default-derived updates with prerequisites and confirm that they fall outside the local class, as Imielinski's theorem predicts; any update inside the class that disagrees refutes the characterization. Third, against Lee and Palla's grounded pipeline, we will plot total time and memory against horizon depth and report the crossover honestly. The proposal succeeds if a crossover exists at horizons realistic for long-lived agents, and fails if grounding wins throughout.
References
- On First-Order Definability and Computability of Progression for Local-Effect Actions and Beyond
- Results on Translating Defaults to Circumscription
- Loop Formulas for Circumscription
- Conflict-Driven Answer Set Solving
- Computing Circumscription Revisited: Preliminary Report
- A Simple Formalization of Actions Using Circumscription
- On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic
- Progression of Decomposed Situation Calculus Theories
- On Action Theories with Iterable First-Order Progression
- Decidable Fragments of First-Order Language Under Stable Model Semantics and Circumscription
- Situation Calculus as Answer Set Programming
- Translating First-Order Theories into Logic Programs
- A Model-Theoretic Counterpart of Loop Formulas
- Embracing Causality in Specifying the Indirect Effects of Actions