Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4: Exponential upper bound on basic functions (pA(v)≤q∣v∣p_A(v) \le q^{|v|}pA​(v)≤q∣v∣)

Proved
HofmannMoser.proposition_4

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

amortized-analysiscomplexityterm-rewritingtree-automatatype-systems

This is Proposition 4 of Hofmann and Moser (TLCA 2015, p. 246), bounding the number of accepting runs of a tree automaton in terms of its state count and the size of the input value.

Let AAA be a bottom-up nondeterministic tree automaton (TreeAutomaton C) with q=A.stateCountq = A.\text{stateCount}q=A.stateCount states, and let vvv be a ground constructor value (Value C) of size ∣v∣=v.size|v| = v.\text{size}∣v∣=v.size (the total number of constructor symbols occurring in vvv). Then the basic resource function pA(v)=A.basic vp_A(v) = A.\text{basic}\,vpA​(v)=A.basicv satisfies

pA(v)≤q∣v∣.p_A(v) \le q^{|v|}.pA​(v)≤q∣v∣.

This bound shows that every basic resource function grows at most exponentially in the size of the input value, and provides the baseline growth estimate refined by polynomial tree automata in Section 5 of the paper.

Formalization Note In TreeAutomaton C, transition lists A.rules n c are duplicate-free (no_duplicate_rules), so for each target state α\alphaα there are at most qnq^nqn transitions c(α1,…,αn)→αc(\alpha_1, \dots, \alpha_n) \to \alphac(α1​,…,αn​)→α.

Preamble
import Definitions.Def_HofmannMoser_Potential

universe u
Formal statement
namespace HofmannMoser

theorem proposition_4 {C : Nat → Type u} (A : TreeAutomaton C) (v : Value C) :
    A.basic v ≤ A.stateCount ^ v.size := 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. 246, Proposition 4
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 node(c,(v0,…,vn−1))\text{node}(c, (v_0, \dots, v_{n-1}))node(c,(v0​,…,vn−1​)), where n∈Nn \in \mathbb{N}n∈N, c∈C(n)c \in C(n)c∈C(n), and v0,…,vn−1∈Value(C)v_0, \dots, v_{n-1} \in \text{Value}(C)v0​,…,vn−1​∈Value(C). The size ∣v∣∈N|v| \in \mathbb{N}∣v∣∈N of a value v=node(c,(v0,…,vn−1))v = \text{node}(c, (v_0, \dots, v_{n-1}))v=node(c,(v0​,…,vn−1​)) is defined recursively as 111 plus the sum of the sizes of its children:

∣node(c,(v0,…,vn−1))∣=1+∑i=0n−1∣vi∣.\big|\text{node}(c, (v_0, \dots, v_{n-1}))\big| = 1 + \sum_{i=0}^{n-1} |v_i|.​node(c,(v0​,…,vn−1​))​=1+i=0∑n−1​∣vi​∣.

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 state A.final∈{0,…,K−1}A.\text{final} \in \{0, \dots, K-1\}A.final∈{0,…,K−1};
  • for each arity n∈Nn \in \mathbb{N}n∈N and constructor c∈C(n)c \in C(n)c∈C(n), a finite duplicate-free list A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) of transition rules ((q0,…,qn−1),q′)∈{0,…,K−1}n×{0,…,K−1}((q_0, \dots, q_{n-1}), q') \in \{0, \dots, K-1\}^n \times \{0, \dots, K-1\}((q0​,…,qn−1​),q′)∈{0,…,K−1}n×{0,…,K−1};
  • proofs that A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) contains no duplicate transitions for every (n,c)(n, c)(n,c), that only finitely many pairs (n,c)∈∑n∈NC(n)(n, c) \in \sum_{n \in \mathbb{N}} C(n)(n,c)∈∑n∈N​C(n) have ∣A.rules(n,c)∣>0|A.\text{rules}(n, c)| > 0∣A.rules(n,c)∣>0, and that at least one pair (n,c)(n, c)(n,c) has ∣A.rules(n,c)∣>0|A.\text{rules}(n, c)| > 0∣A.rules(n,c)∣>0.

For any state q∈{0,…,K−1}q \in \{0, \dots, K-1\}q∈{0,…,K−1} and value v=node(c,(v0,…,vn−1))∈Value(C)v = \text{node}(c, (v_0, \dots, v_{n-1})) \in \text{Value}(C)v=node(c,(v0​,…,vn−1​))∈Value(C), the run count runCount(A,v,q)∈N\text{runCount}(A, v, q) \in \mathbb{N}runCount(A,v,q)∈N is defined recursively by

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

where the product over i∈{0,…,n−1}i \in \{0, \dots, n-1\}i∈{0,…,n−1} is a left fold of multiplication starting from 111. The basic function of AAA at vvv is A.basic(v)=runCount(A,v,A.final)∈NA.\text{basic}(v) = \text{runCount}(A, v, A.\text{final}) \in \mathbb{N}A.basic(v)=runCount(A,v,A.final)∈N.

Given any tree automaton A:TreeAutomaton(C)A : \text{TreeAutomaton}(C)A:TreeAutomaton(C) and any value v∈Value(C)v \in \text{Value}(C)v∈Value(C), this theorem asserts the inequality in N\mathbb{N}N:

A.basic(v)≤(A.stateCount)∣v∣.A.\text{basic}(v) \le (A.\text{stateCount})^{|v|}.A.basic(v)≤(A.stateCount)∣v∣.

Edge and degenerate cases:

  • Because A.finalA.\text{final}A.final inhabits {0,…,A.stateCount−1}\{0, \dots, A.\text{stateCount}-1\}{0,…,A.stateCount−1}, A.stateCount≥1A.\text{stateCount} \ge 1A.stateCount≥1 holds for every tree automaton AAA (A.stateCount=0A.\text{stateCount} = 0A.stateCount=0 is impossible).
  • For every value v∈Value(C)v \in \text{Value}(C)v∈Value(C), ∣v∣≥1|v| \ge 1∣v∣≥1, with ∣v∣=1|v| = 1∣v∣=1 when v=node(c,())v = \text{node}(c, ())v=node(c,()) is a leaf (n=0n = 0n=0).
  • The duplicate-freeness condition on A.rules(n,c)A.\text{rules}(n, c)A.rules(n,c) is built into the structure TreeAutomaton(C)\text{TreeAutomaton}(C)TreeAutomaton(C) and bounds the number of transitions with a given child-state tuple (q0,…,qn−1)(q_0, \dots, q_{n-1})(q0​,…,qn−1​) and target state q′q'q′.
  • If C(0)C(0)C(0) is empty, Value(C)\text{Value}(C)Value(C) is uninhabited and the statement holds vacuously.
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