Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3: Recursive decomposition of basic functions

Proved
HofmannMoser.proposition_3

by kmehltretter82 · Oct 28, 2026 · Mathlib c5ea003 (Lean v4.30.0)

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Proposition 3 of Hofmann and Moser (TLCA 2015, p. 245), giving the bottom-up recursive decomposition of the basic resource function associated with a tree automaton.

Let C\mathcal{C}C be an arity-indexed constructor signature (C : Nat → Type u), let AAA be a bottom-up nondeterministic tree automaton over C\mathcal{C}C (TreeAutomaton C), let c∈Cnc \in \mathcal{C}_nc∈Cn​ be an nnn-ary constructor applied to ground constructor values v1,…,vnv_1, \dots, v_nv1​,…,vn​ (vs : Fin n → Value C), and let α∈Fin⁡(A.stateCount)\alpha \in \operatorname{Fin}(A.\text{stateCount})α∈Fin(A.stateCount) be a state of AAA. Write (A,q)(A, q)(A,q) for the automaton AAA rerooted at final state qqq (A.reroot q) and p(A,q)p_{(A, q)}p(A,q)​ for its basic resource function (A.reroot q).basic. Then

p(A,α)(c(v1,…,vn))=∑((α1,…,αn),α)∈ΔA(c)∏i=1np(A,αi)(vi).p_{(A, \alpha)}(c(v_1, \dots, v_n)) = \sum_{((\alpha_1, \dots, \alpha_n), \alpha) \in \Delta_A(c)} \prod_{i=1}^n p_{(A, \alpha_i)}(v_i).p(A,α)​(c(v1​,…,vn​))=((α1​,…,αn​),α)∈ΔA​(c)∑​i=1∏n​p(A,αi​)​(vi​).

This identity underpins the constructor typing rule and the potential-preservation theorem for the additive constructor shift ◃c\triangleleft_c◃c​ (Lemma 12).

Formalization Note The sum ranges over the filtered transition list (A.rules n c).filter (fun tr ↦ tr.2 == α) and the product over Fin n is computed via (List.ofFn ...).foldl (· * ·) 1, so the empty product for a nullary constructor (n=0n = 0n=0) evaluates to 111.

Preamble
import Definitions.Def_HofmannMoser_Potential

universe u
Formal statement
namespace HofmannMoser

theorem proposition_3 {C : Nat → Type u} (A : TreeAutomaton C) {n : Nat}
    (c : C n) (vs : Fin n → Value C) (α : Fin A.stateCount) :
    (A.reroot α).basic (.node c vs) =
      (((A.rules n c).filter (fun tr ↦ tr.2 == α)).map fun tr ↦
        (List.ofFn fun i ↦ (A.reroot (tr.1 i)).basic (vs i)).foldl (· * ·) 1).sum := by sorry

end HofmannMoser
Source
Hofmann--Moser 2015, Multivariate Amortised Resource Analysis for Term Rewrite Systems, TLCA 2015, https://doi.org/10.4230/LIPIcs.TLCA.2015.241, Section 3, p. 245, Proposition 3
Read-back

What the Lean code literally says, in plain math · gemini-2.5-pro

Let C:N→Type uC : \mathbb{N} \to \text{Type } uC:N→Type u be an arity-indexed family of constructor symbol types in universe uuu. A value v∈Value(C)v \in \text{Value}(C)v∈Value(C) is a finite constructor tree generated inductively by nodes of the form node(c′,(w0,…,wk−1))\text{node}(c', (w_0, \dots, w_{k-1}))node(c′,(w0​,…,wk−1​)), where k∈Nk \in \mathbb{N}k∈N is an arity, c′∈C(k)c' \in C(k)c′∈C(k) is a constructor symbol of arity kkk, and (w0,…,wk−1):{0,…,k−1}→Value(C)(w_0, \dots, w_{k-1}) : \{0, \dots, k-1\} \to \text{Value}(C)(w0​,…,wk−1​):{0,…,k−1}→Value(C) is a kkk-tuple of child values. A tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C) over CCC consists of:

  • a natural number of states K=A.stateCount∈NK = A.\text{stateCount} \in \mathbb{N}K=A.stateCount∈N, with state space {0,…,K−1}\{0, \dots, K-1\}{0,…,K−1};
  • a designated final (root) state A.final∈{0,…,K−1}A.\text{final} \in \{0, \dots, K-1\}A.final∈{0,…,K−1};
  • for each arity k∈Nk \in \mathbb{N}k∈N and constructor c′∈C(k)c' \in C(k)c′∈C(k), a finite list A.rules(k,c′)A.\text{rules}(k, c')A.rules(k,c′) of transition rules ((q0,…,qk−1),q′)∈{0,…,K−1}k×{0,…,K−1}((q_0, \dots, q_{k-1}), q') \in \{0, \dots, K-1\}^k \times \{0, \dots, K-1\}((q0​,…,qk−1​),q′)∈{0,…,K−1}k×{0,…,K−1}, where (q0,…,qk−1)(q_0, \dots, q_{k-1})(q0​,…,qk−1​) is a kkk-tuple of child states and q′q'q′ is the target parent state;
  • proofs that A.rules(k,c′)A.\text{rules}(k, c')A.rules(k,c′) has no duplicate entries for every (k,c′)(k, c')(k,c′), that only finitely many pairs (k,c′)(k, c')(k,c′) in ∑k∈NC(k)\sum_{k \in \mathbb{N}} C(k)∑k∈N​C(k) have a nonempty rule list A.rules(k,c′)A.\text{rules}(k, c')A.rules(k,c′), and that at least one pair (k,c′)(k, c')(k,c′) has a nonempty rule list.

For any tree automaton B:TreeAutomaton(C)B : \text{TreeAutomaton}(C)B:TreeAutomaton(C), value w=node(c′,(w0,…,wk−1))∈Value(C)w = \text{node}(c', (w_0, \dots, w_{k-1})) \in \text{Value}(C)w=node(c′,(w0​,…,wk−1​))∈Value(C), and state q∈{0,…,B.stateCount−1}q \in \{0, \dots, B.\text{stateCount}-1\}q∈{0,…,B.stateCount−1}, the run count runCount(B,w,q)∈N\text{runCount}(B, w, q) \in \mathbb{N}runCount(B,w,q)∈N is defined recursively by filtering B.rules(k,c′)B.\text{rules}(k, c')B.rules(k,c′) to those transitions tr=((q0,…,qk−1),q′)\text{tr} = ((q_0, \dots, q_{k-1}), q')tr=((q0​,…,qk−1​),q′) whose target state q′q'q′ equals qqq, mapping each such transition to the left-folded product ∏i=0k−1runCount(B,wi,qi)\prod_{i=0}^{k-1} \text{runCount}(B, w_i, q_i)∏i=0k−1​runCount(B,wi​,qi​) (starting from 111), and summing the resulting products over the filtered list. The basic function of BBB evaluated at www is B.basic(w)=runCount(B,w,B.final)B.\text{basic}(w) = \text{runCount}(B, w, B.\text{final})B.basic(w)=runCount(B,w,B.final). For any state q∈{0,…,A.stateCount−1}q \in \{0, \dots, A.\text{stateCount}-1\}q∈{0,…,A.stateCount−1}, the rerooted automaton A.reroot(q)A.\text{reroot}(q)A.reroot(q) is identical to AAA (same state count and transition rules) except that its designated final state is set to qqq.

Given any tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C), any arity n∈Nn \in \mathbb{N}n∈N, any constructor symbol c∈C(n)c \in C(n)c∈C(n), any nnn-tuple of values (v0,…,vn−1):{0,…,n−1}→Value(C)(v_0, \dots, v_{n-1}) : \{0, \dots, n-1\} \to \text{Value}(C)(v0​,…,vn−1​):{0,…,n−1}→Value(C), and any state α∈{0,…,A.stateCount−1}\alpha \in \{0, \dots, A.\text{stateCount}-1\}α∈{0,…,A.stateCount−1}, this theorem asserts the equality in N\mathbb{N}N:

(A.reroot(α)).basic(node(c,(v0,…,vn−1)))=∑((q0,…,qn−1),q′)∈A.rules(n,c)q′=α∏i=0n−1(A.reroot(qi)).basic(vi),(A.\text{reroot}(\alpha)).\text{basic}\big(\text{node}(c, (v_0, \dots, v_{n-1}))\big) = \sum_{\substack{((q_0, \dots, q_{n-1}), q') \in A.\text{rules}(n, c) \\ q' = \alpha}} \prod_{i=0}^{n-1} (A.\text{reroot}(q_i)).\text{basic}(v_i),(A.reroot(α)).basic(node(c,(v0​,…,vn−1​)))=((q0​,…,qn−1​),q′)∈A.rules(n,c)q′=α​∑​i=0∏n−1​(A.reroot(qi​)).basic(vi​),

where the product over i∈{0,…,n−1}i \in \{0, \dots, n-1\}i∈{0,…,n−1} is computed by a left fold of multiplication starting from 111 over the list of values (A.reroot(qi)).basic(vi)(A.\text{reroot}(q_i)).\text{basic}(v_i)(A.reroot(qi​)).basic(vi​), and the sum is taken in list order over the transitions in A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) whose second component equals α\alphaα.

Edge and degenerate cases:

  • The state count A.stateCountA.\text{stateCount}A.stateCount cannot be 000, because A.finalA.\text{final}A.final (and α\alphaα) inhabit {0,…,A.stateCount−1}\{0, \dots, A.\text{stateCount}-1\}{0,…,A.stateCount−1}.
  • When n=0n = 0n=0 (so c∈C(0)c \in C(0)c∈C(0) is a nullary leaf constructor and (v0,…,vn−1)(v_0, \dots, v_{n-1})(v0​,…,vn−1​) is the empty tuple), the inner left-folded product over the empty list evaluates to 111, so each transition ((()),α)∈A.rules(0,c)((()), \alpha) \in A.\text{rules}(0, c)((()),α)∈A.rules(0,c) contributes 111 to the sum.
  • When A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) contains no transition with target state α\alphaα, the filtered list is empty and both sides equal 000.
  • If C(0)C(0)C(0) is empty, the inductive type Value(C)\text{Value}(C)Value(C) is uninhabited; in that case, for n>0n > 0n>0 no tuple (v0,…,vn−1)(v_0, \dots, v_{n-1})(v0​,…,vn−1​) exists and for n=0n = 0n=0 no constructor c∈C(0)c \in C(0)c∈C(0) exists, making the quantification vacuous.
Human review
  • Endorsed by Shuze Chen · Oct 28, 2026

    Confirmed by the moderator at approval.

  • Endorsed by kmehltretter82 · Oct 28, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me