Automated theorem provers, programs that search for formal proofs, struggle with operators that are associative and commutative (AC), such as addition, multiplication, union and conjunction. If the AC laws are given to the prover as ordinary axioms, it loops forever swapping and regrouping arguments. If the laws are instead built into unification (the step that decides whether two terms can be made identical by substituting for variables), each successful match can produce an enormous set of distinct solutions, and the prover must start a separate branch for each one. The size of that set can grow doubly exponentially. This note proposes a middle course. When two clauses clash modulo AC, the prover emits a single resolvent that carries the unsolved AC equation as an attached constraint. It checks only that the constraint is solvable, and it expands the constraint into concrete substitutions only when a proof actually needs them.
The reason to expect a large gain is arithmetic. An eager prover pays for every member of every complete unifier set at every clash. A lazy prover pays one cheap solvability check per clash and enumerates solutions only along the few branches that reach a proof. The idea also links three older lines of work. Universal unification theory says when such deferred enumeration is still complete. AC complexity results say which cheap checks are sound filters. Theory resolution provides the inference form into which the constraints fit.
Core Claim
Our central claim concerns "lazy AC theory resolution." This is a resolution calculus in which a clash between literals $L$ and $\neg L'$ that are AC-unifiable but not syntactically unifiable yields one clause $C \lor D \;\|\; L \doteq_{AC} L'$. The part after $\|$ is an AC unification constraint attached to the clause and is never solved eagerly. We claim this calculus is refutationally complete for theories in Siekmann and Szabó's regular ACFM class. On AC-heavy first-order problems, we claim it generates far fewer clauses than eager AC unification, and that it does so without the per-step CPU overhead that erased the gains of earlier embedded-inference systems.
The expected clause saving can be written simply. Let $\mathcal{K}$ be the set of AC clashes the prover attempts, and let $\mathrm{CSU}(k)$ be the minimal complete set of AC unifiers for clash $k$. An eager prover then adds $\sum_{k \in \mathcal{K}} |\mathrm{CSU}(k)|$ resolvents. The lazy prover adds only $|\{k \in \mathcal{K} : \mathrm{filter}(k) = \text{pass}\}|$ resolvents, plus the enumeration performed later along successful branches. The ratio between the two counts is our main predicted effect. It should grow with the average unifier-set size, which is exactly where the doubly exponential worst case lives.
Grounding in Prior Work
The motivating evidence comes from two places. Stickel's AC algorithm, A Complete Unification Algorithm for Associative-Commutative Functions, reduces AC unification to finding a basis of minimal non-negative solutions of linear Diophantine equations. It then builds the full unifier set from that basis eagerly, and that eager construction is the cost we remove. Bachmair and colleagues, in Leo Bachmair, (Experiments with Associative-Commutative Discrimination Nets), report that matching and rewriting can take up to 90% of an equational prover's time. Together these show that AC work dominates and that eager enumeration is the expensive part.
Our technique draws on three sources. Stickel's Automated Deduction by Theory Resolution supplies the "partial theory resolution" inference, in which a clash succeeds conditionally and leaves a residue. It treats the theory reasoner as a black box that must return its residue at once. We change two things: the residue becomes a deferred unification constraint, and the theory module gets a richer interface. Experiments with Associative-Commutative Discrimination Nets supplies the cheap necessary-condition check. Its polynomial-time "linearized" matching stage treats repeated variables as distinct and, on uqsl2, rejected all patterns in 88% of cases. We reuse this stage, together with a linear relaxation of Stickel's Diophantine system, as the solvability filter on constraints. Universal Unification and Regular Equational ACFM Theories shows that for regular theories, where both sides of each axiom contain the same variables, the most general unifiers can be listed one by one in an enumeration that eventually reaches every one of them. That is the property a lazy calculus needs so that deferred enumeration never loses a solution. The authors also call their own enumerator impractical. We do not run it as a search procedure; we use it only as the completeness argument.
Several papers constrain the design. Marché's Equational Reasoning using AC Constraints is the closest existing work. It also avoids full AC unification, but it does so with ordering constraints inside unfailing completion, the procedure that turns equations into rewrite rules. It works only on purely equational problems, and its inconsistency test (Theorem 4.5) is sufficient but not necessary. Our method is different in kind. It places unification constraints into general clausal resolution with non-unit clauses and predicates, which completion does not handle.
Digricoli's The Efficacy of RUE Resolution Experimental Results and Heuristic Theory is the main cautionary result. RUE also emits a deferred object, a disagreement set of mismatched subterms that must be made equal. It cut unifications by orders of magnitude, yet it lost on CPU time to the paramodulation prover MOW on group theory. Any lazy scheme can repeat that failure if its constraints pile up. We therefore treat bounding the cost per inference as a first-class design problem rather than an afterthought.
Veroff and Henschen's Application of Automatic Transformations to Program Verification obtained up to 50% shorter proofs by building commutativity-like transformations into clashing. They did so with hand-picked transformation lists and gave up completeness. Our calculus aims to keep their compression while deriving the behavior from the theory itself and keeping completeness.
The file does not index the wider literature on constrained deduction beyond these papers. Part of the first work package is to position the calculus against that literature, rather than assume no one has studied deferred unification constraints.
Research Program
The first component is the calculus and its completeness proof. Constrained clauses come with four rules. Constrained resolution and factoring conjoin new AC constraints to the existing ones. A cheap filter deletes clauses whose constraint conjunction is shown unsolvable. A forced-solve rule replaces a clause by its instances under a prefix of the enumerated unifiers. Refutation means deriving the empty clause with a solvable constraint.
The completeness argument has three steps. We lift ground refutations to constrained clauses. The filter is sound because it rejects only unsolvable constraints. The Siekmann–Szabó enumerability result for regular theories then ensures that forced solving, scheduled fairly, eventually produces any unifier a ground proof requires. Associativity alone is excluded on purpose. A Hierarchical Approach to Theorem-Proving notes that it yields infinitely many most general unifiers. The calculus would still be complete in the limit there, but a constraint could never be fully expanded.
The second component is a small universal interface for theories. Each theory module provides three operations: a sound polynomial-time necessary condition, a decision or semi-decision of unifiability, and an on-demand unifier stream. We implement modules for commutativity (C), AC, and AC with idempotency (ACI). The ACI module uses the two-phase method of Unification of Idempotent Functions. These modules test whether "universal" means more than AC. Only the modules differ; the resolution core stays the same.
The third component is a forced-solve policy that addresses the RUE problem directly. A constraint is expanded when either of two things happens. One trigger is that its conjunction size passes a threshold $\tau$. The other is that the clause is selected as a candidate for the empty clause or for subsumption. We use van Vaalen's result in An Extension of Unification to Substitution with an Application to Automatic Theorem Proving as a design hypothesis. In the syntactic case, his result says that unifying the substitutions from independent subproblems gives the same most general unifier as solving all equations at once. We test empirically whether solving constraint conjunctions piece by piece modulo AC avoids the blowup of solving them simultaneously. Extending his theorem to AC is an open question, not something we assume.
Baselines
The naive reference point is the same resolution core with the AC axioms supplied as ordinary clauses and no theory module. It shares the clause-selection heuristics, time limit and memory cap with every other configuration. This shows the cost of doing nothing. Its expected behavior is set by figures in the file: explicit axiomatization of Schubert's Steamroller needed nearly 3 minutes and 2,717 formulas in Automated Deduction by Theory Resolution.
The strongest same-architecture competitor is eager AC theory resolution. It uses the same core but calls Stickel's Diophantine algorithm at every clash and creates one resolvent per unifier. Because only the unification step differs, this is the comparison that isolates laziness. Lazy beats eager if it solves strictly more problems under the same limit, and if on problems both solve it generates at least 2x fewer clauses with no median CPU slowdown. We give eager every advantage by also running it with the AC discrimination net from Experiments with Associative-Commutative Discrimination Nets as an indexing filter. That paper reports up to a 2.2x reduction in execution time on complex AC problems. To rule out a mere indexing effect, our gain over the net-equipped eager prover must exceed what the net alone provides.
The strongest existing method on purely equational AC problems is Marché's consistent unfailing completion. On Lusk–Overbeek problem E6, Equational Reasoning using AC Constraints reports 5,928 critical pairs and 64 rules with AC constraints. Without them it needed over 15,000 critical pairs and 137,138 rules. It also solved all six problems E1–E6. We compare on these problems by reimplementing his CUCP and PERM rules under our time budget, and we also quote his published counts. Matching his solve rate there is the bar. Beating him on equational problems is not claimed, since completion is a different and specialized setting.
On equality problems with an RUE comparison, the reported reference points are as follows. For Boolean algebra problem B1, RUE needed 42 unifications and MOW needed 26,702. For ring theory problem R1, RUE needed 114 and MOW 12,328, as reported in The Efficacy of RUE Resolution Experimental Results and Heuristic Theory. The file gives no per-problem CPU seconds for the group theory cases. For those we will report CPU time ourselves for an RUE reimplementation and for the lazy prover.
Three ablations isolate the key ingredients. Lazy-without-filter keeps constraints but never runs the cheap check, which measures what the discrimination-net stage contributes. A sweep of $\tau$ from 1, which is effectively eager, to unbounded maps the trade-off between compression and overhead. Finally, the lazy calculus is run with only the C module on AC problems, to check that the benefit comes from AC structure rather than from constraint bookkeeping.
Why not just…?
Why not just give a modern prover the AC axioms? The file's evidence against this is strong, though old. Explicit commutativity loops, and the Steamroller and E6 figures above show search spaces one to three orders of magnitude larger. The file has no measurements of current provers. We will therefore include whatever current provers are available as additional untuned baselines and report them, and we will not claim a win over systems the file does not cover.
Why not just plug Stickel's eager AC unification into resolution, with a discrimination net in front? This is the real competitor, and it is our main baseline. The case for laziness is the clause-count ratio in the core equation. The net speeds up retrieval but cannot shrink $|\mathrm{CSU}(k)|$, and its bipartite-matching tables stop at rank 5. If the eager prover with the net matches the lazy prover on solve rate and CPU time, the proposal fails. The $\tau$ sweep shows directly where, if anywhere, the two diverge.
Why not just encode everything equationally and run Marché's AC-constrained completion? On unit equational problems this may well be as good or better, and we expect a tie at best on E1–E6 and the ring problems. The contribution only matters for non-unit clauses mixing predicates with AC operators. Examples are the program verification problems of Application of Automatic Transformations to Program Verification, where symmetric and commutative predicates such as EQUAL appear, and Steamroller-style taxonomies extended with AC set operations. Encoding these equationally is possible but adds encoding axioms. We will run both, and if completion on the encoding wins, we will report that.
Why not just use RUE-style disagreement sets, which are already lazy? RUE defers syntactic equality, not AC equivalence, and its per-step cost beat it on CPU time in group theory. Our filter-plus-threshold design responds to that failure. The CPU-time comparison on the RUE suite is the experiment that tests whether we have repeated it.
Proposed Experiments
The benchmarks come from the file. The Lusk–Overbeek problems E1–E6 and the ring problems wos21, RNG015-6, RNG023-6 and RNG024-6 cover equational AC. The 17-problem RUE suite covers Boolean algebra, rings and groups. The 11 Veroff–Henschen program verification problems and their noise variants cover non-unit clauses with commutative predicates. Schubert's Steamroller serves as a control with no AC structure, where the lazy prover should show no regression. We will also build a mixed suite: Steamroller-style and verification problems in which set or arithmetic operators are AC. The file contains no such suite, which is a weakness of the evidence we must repair ourselves.
The metrics are problems solved within a fixed time limit, clauses generated and kept, unifier computations, CPU time, and proof depth.
The decisive checks are three. First, on the mixed suite, the lazy prover must solve more problems than eager-plus-net under the same limit. Second, on problems both solve, the measured clause ratio should track the average $|\mathrm{CSU}|$ that we log from the eager run; a flat ratio would mean the predicted mechanism is not what drives any gains. Third, on RUE group theory, median CPU time must not exceed eager's at the best $\tau$. If the lazy prover reduces clauses but loses on CPU time the way RUE did, the result is negative, and we will report it as such.
References
- A Complete Unification Algorithm for Associative-Commutative Functions
- Experiments with Associative-Commutative Discrimination Nets
- Automated Deduction by Theory Resolution
- Experiments with Associative-Commutative Discrimination Nets
- Universal Unification and Regular Equational ACFM Theories
- Equational Reasoning using AC Constraints
- The Efficacy of RUE Resolution Experimental Results and Heuristic Theory
- Application of Automatic Transformations to Program Verification
- A Hierarchical Approach to Theorem-Proving
- Unification of Idempotent Functions
- An Extension of Unification to Substitution with an Application to Automatic Theorem Proving