Proposition 4: Exponential upper bound on basic functions ()
ProvedHofmannMoser.proposition_4This 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 be a bottom-up nondeterministic tree automaton (TreeAutomaton C) with states, and let be a ground constructor value (Value C) of size (the total number of constructor symbols occurring in ). Then the basic resource function satisfies
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 there are at most transitions .
import Definitions.Def_HofmannMoser_Potential universe u
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 HofmannMoserRead-back
What the Lean code literally says, in plain math · gemini-2.5-pro
Let be an arity-indexed family of constructor symbol types in universe . A value is a finite constructor tree generated inductively by nodes , where , , and . The size of a value is defined recursively as plus the sum of the sizes of its children:
A tree automaton over consists of:
- a natural number of states , with state space ;
- a designated final state ;
- for each arity and constructor , a finite duplicate-free list of transition rules ;
- proofs that contains no duplicate transitions for every , that only finitely many pairs have , and that at least one pair has .
For any state and value , the run count is defined recursively by
where the product over is a left fold of multiplication starting from . The basic function of at is .
Given any tree automaton and any value , this theorem asserts the inequality in :
Edge and degenerate cases:
- Because inhabits , holds for every tree automaton ( is impossible).
- For every value , , with when is a leaf ().
- The duplicate-freeness condition on is built into the structure and bounds the number of transitions with a given child-state tuple and target state .
- If is empty, is uninhabited and the statement holds vacuously.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.