Static resource analysis aims to derive machine-checkable upper bounds on the computational cost of a program without executing it on every input. In Tarjan's potential method (1985), each program state is assigned a nonnegative potential so that the drop in potential across a step pays for both its immediate cost and the potential required by subsequent operations. Hofmann and Jost (POPL 2003) turned the potential method into a type-and-effect system—automatic amortised resource analysis (AARA)—capable of inferring linear heap-space bounds for first-order functional programs via linear programming. Hoffmann, Aehlig, and Hofmann (TOPLAS 2012) extended AARA to multivariate polynomial bounds for fixed data types such as lists and binary trees by indexing resource annotations with predetermined binomial basis functions.
In Multivariate Amortised Resource Analysis for Term Rewrite Systems (TLCA 2015), Martin Hofmann and Georg Moser generalize multivariate AARA from fixed built-in types to arbitrary constructor term rewrite systems (TRSs) over user-defined inductive data structures. Instead of hard-coding polynomial basis functions per type, they generate the basis of basic resource functions uniformly as the accepting-run counts of bottom-up nondeterministic tree automata over the constructor signature. This framework encompasses arbitrary constructor trees while reducing resource verification of rewrite rules to linear constraints over annotation coefficients.
Let and be arity-indexed families of constructor symbols (C : Nat → Type u) and defined function symbols (D : Nat → Type u). First-order terms (Term C D) are built from variables (Term.var x), constructor applications , and defined applications . A ground constructor value (Value C) is a variable-free term constructed solely from symbols in ; its size (Value.size) is the total number of constructor nodes in , and Value.toTerm embeds values injectively into terms (IsValue).
A term rewrite system (RewriteSystem C D) is a predicate on rewrite rules (RewriteRule C D) of the form . Standing syntactic conditions (FiniteConstructors C, FiniteSignature C D, FiniteSystem R, SyntacticallyOrthogonal R, CompletelyDefined R) require that is finite and nonempty, is finite with at least one constant, is finite, each rule is left-linear with constructor patterns that are pairwise non-overlapping, and every ground call matches some rule in . Under a normalised substitution (Substitution.Normalised, mapping every variable in to a constructor value), the big-step judgment (Evaluates R σ t m v.toTerm) states that evaluates to value in counted innermost rewrite steps.
A bottom-up nondeterministic tree automaton (TreeAutomaton C) consists of a finite state space , a designated final state , and duplicate-free transition lists for each -ary constructor . For any state , the run count (A.runCount v q) on is defined recursively by
and the basic function computed by is (A.basic). The type of basic resource functions is (BasicFunction C). A representative policy (RepPolicy C) selects one representative automaton for each satisfying , formalizing the fixed enumeration of Sections 3–4. Given , the multivariate basic function (multivariateBasic) is
A resource annotation of length (Annotation C n) is a finite list of pairs with and , representing the finitely supported coefficient family (annotationCoefficient). Its potential (potential) on values is
A unary function is a resource function (IsResourceFunction C r) if for some length- annotation . The additive shift (additiveShift P c Q) expands the last coordinate of each tuple in a length- annotation along the -transitions into the final state of , replacing by the rerooted child basic functions . The sharing operator (annotationShare S P Q) contracts the last two coordinates of a length- annotation via the Cartesian-product basic function BasicFunction.product S P.
Finally, an annotated signature pair (AnnotatedSignatures C D) provides charged (counted, ) and uncharged (costFree, ) signature relations (AnnotatedSignature C D). The resource typing judgment (Typing S P F mode n xs Q t Q') formalizes the inference rules of Figure 2 (variable, defined call, constructor, annotation weakening, simultaneous context/annotation exchange, context weakening via projection at the canonical one-state basic function , variable sharing, and -ary function/constructor composition governed by compositionCoefficients and listPremiseMode). A rewrite system is bounded (BoundedSignatures S P F R) if every rule in and every signature entry for admits an iterated constructor pattern expansion (PatternExpansion) of and into variables and an annotation such that holds with in counted mode and in cost-free mode.
HofmannMoser.theorem_16, p. 252)For a finite, completely defined, syntactically orthogonal constructor TRS over a finite signature that is bounded (BoundedSignatures S P F R) with respect to extensional annotated signatures , if is derivable in counted mode for a context of distinct variables and holds for a normalised substitution mapping each to a constructor value , then
HofmannMoser.proposition_3, p. 245) — Recursive decomposition of the basic function at a constructor node :HofmannMoser.proposition_4, p. 246) — Exponential upper bound on the number of accepting runs of a -state tree automaton on a value of size :HofmannMoser.lemma_7, p. 247) — Closure of the class of resource functions over a finite nonempty constructor signature under pointwise addition and pointwise multiplication:HofmannMoser.lemma_9, p. 248) — Diagonalization of binary multivariate basic functions via the Cartesian-product automaton:HofmannMoser.lemma_12, p. 248) — Potential preservation across the additive constructor shift :HofmannMoser.lemma_13, p. 249) — Potential preservation across the variable-sharing operator :The result itself. Theorem 16 is the core soundness theorem of multivariate amortised resource analysis for term rewrite systems: it guarantees that syntactic typing constraints on rewrite rules suffice to bound the dynamic number of innermost evaluation steps on all ground constructor inputs. Together with Proposition 4 and polynomial growth conditions on the automata occurring in an annotation, Theorem 16 yields concrete polynomial and exponential complexity bounds for first-order functional programs presented as TRSs.
Formalizing it. While Hofmann and Moser proved Theorem 16 on paper (TLCA 2015, pp. 252–254) and univariate amortised complexity of functional data structures has been formalized in Isabelle/HOL (Nipkow and Brinkop 2019), no machine-checked formalization of Hofmann and Moser's multivariate tree-automata framework existed in Lean 4. A faithful formalization also resolves a subtle indexing ambiguity in the printed text of Section 3: because nondeterministic automata with identical accepted languages can have different accepting-run counts, and distinct automata with the same run-count function can have incompatible state spaces under constructor shifting, the formal development separates extensional basic functions (BasicFunction C) from the fixed representative policy (RepPolicy C) used by constructor shifts. In our local verification suite, all six milestones (Propositions 3 and 4, Lemmas 7, 9, 12, and 13) have been machine-checked in Lean 4.30 to validate the definitions; the published mission items open these milestones and the full soundness proof of Theorem 16 on the platform.
Two main obstacles arise when formalizing this paper:
annotationShare) must match basic functions occurring in signature annotations (BasicFunction). Conversely, indexing purely by accepted languages fails because run counts are not language-invariant, and Definition 11's printed equation (1) on p. 248 must reroot the same parent representative at its child states rather than matching state labels across unrelated automata.Typing.composition), a function or constructor symbol has arbitrary positive arity , its argument contexts are concatenated via argumentContexts, and the intermediate annotations and are coupled through the coefficient equations of compositionCoefficients and the mode switch listPremiseMode (which charges the single all-canonical index and treats all non-canonical indices as cost-free). Proving the telescoping potential inequality across all argument evaluations and combining it with the pattern-expansion induction for BoundedSignatures is the central proof obligation of Theorem 16.The development is written in core Lean 4 (v4.30.0, without Mathlib) across three foundational definition modules:
Definitions.Def_HofmannMoser_Syntax: arity-indexed terms (Term), ground constructor predicates (IsValue), variable lists, variable renaming, finite-domain substitutions (Substitution, Substitution.Normalised), rewrite rules (RewriteRule), syntactic orthogonality (SyntacticallyOrthogonal), complete definedness (CompletelyDefined), and big-step innermost evaluation (Evaluates).Definitions.Def_HofmannMoser_Potential: ground constructor trees (Value), value size (Value.size), finite constructor signatures (FiniteConstructors), bottom-up tree automata (TreeAutomaton), canonical and rerooted automata (canonical, reroot), Cartesian-product automata (product with an unreachable padding state ensuring nonemptiness of transition sets), basic functions (BasicFunction), representative policies (RepPolicy, classicalRepPolicy), annotations (Annotation), potentials (potential), additive shifts (additiveShift), and sharing (annotationShare).Definitions.Def_HofmannMoser_Typing: charged and cost-free modes (TypingMode), annotated signatures (AnnotatedSignature, AnnotatedSignatures, AnnotatedSignatureExtensional), annotation coefficient lookup (annotationCoefficient, annotationCoefficientList), -ary composition constraints (compositionCoefficients), in-place pattern and annotation shifting (PatternExpansion, additiveShiftAt), the resource typing judgment (Typing), and syntactic rule boundedness (Bounded, BoundedSignatures).To prevent any trivializing formalization, BoundedSignatures is defined strictly via syntactic left-hand-side constructor pattern expansion (PatternExpansion) and typing of rule right-hand sides (Definition 15), never by assuming semantic step-count soundness on rewrite steps. Contributions proving the six milestones, intermediate substitution and pattern-expansion lemmas for PatternExpansion and additiveShiftAt, and the main induction for Theorem 16 are welcome.
namespace HofmannMoser
theorem theorem_16 {C D : Nat → Type u}
(S : FiniteConstructors C) (P : RepPolicy C)
(F : AnnotatedSignatures C D) (R : RewriteSystem C D)
(hFinSig : FiniteSignature C D)
(hFinSys : FiniteSystem R)
(hOrth : SyntacticallyOrthogonal R)
(hCompDef : CompletelyDefined R)
(hExtCounted : AnnotatedSignatureExtensional F.counted)
(hExtCostFree : AnnotatedSignatureExtensional F.costFree)
(hBounded : BoundedSignatures S P F R)
{n : Nat} (xs : Fin n → Nat) (hDistinct : Function.Injective xs)
(Q : Annotation C n) (t : Term C D) (Q' : Annotation C 1)
(hType : Typing S P F .counted n xs Q t Q')
(σ : Substitution C D) (hNorm : σ.Normalised)
(vs : Fin n → Value C)
(hDom : ∀ i, xs i ∈ σ.dom)
(hSubst : ∀ i, σ.assignment (xs i) = (vs i).toTerm)
(m : Nat) (v : Value C)
(hEval : Evaluates R σ t m v.toTerm) :
potential Q vs - potential Q' (fun _ ↦ v) ≥ (m : Rat) := by sorry
end HofmannMoserThis is Theorem 16 of Hofmann and Moser (TLCA 2015, p. 252), the main soundness theorem of multivariate amortised resource analysis for term rewrite systems.
Assume the standing conditions of Sections 2–4:
FiniteConstructors C), is a finite overall signature with at least one constant (FiniteSignature C D), and is a representative policy (RepPolicy C).FiniteSystem R), syntactically orthogonal (SyntacticallyOrthogonal R), and completely defined (CompletelyDefined R) constructor term rewrite system.AnnotatedSignatures C D) consists of extensional counted and cost-free annotated signatures (AnnotatedSignatureExtensional F.counted and AnnotatedSignatureExtensional F.costFree) such that is bounded with respect to (BoundedSignatures S P F R).xs : Fin n → Nat) is a context of pairwise distinct variables (Function.Injective xs), is a length- input annotation (Annotation C n), is a term (Term C D), is a length- output annotation (Annotation C 1), and is derivable in counted mode (Typing S P F .counted n xs Q t Q').Substitution C D) is a normalised substitution (σ.Normalised) such that every context variable lies in with ((vs i).toTerm) for ground constructor values (vs : Fin n → Value C).If evaluates under to a ground constructor value (v.toTerm) in innermost rewrite steps (Evaluates R σ t m v.toTerm), then the difference between the input potential and the output potential bounds the step count :
This theorem guarantees that any static resource bound derived in the type system of Figure 2 is a sound upper bound on the number of innermost evaluation steps on all ground constructor inputs.
No open leaves. Every sub-goal is proved or awaiting decomposition.