Proposition 3: Recursive decomposition of basic functions
ProvedHofmannMoser.proposition_3This 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 be an arity-indexed constructor signature (C : Nat → Type u), let be a bottom-up nondeterministic tree automaton over (TreeAutomaton C), let be an -ary constructor applied to ground constructor values (vs : Fin n → Value C), and let be a state of . Write for the automaton rerooted at final state (A.reroot q) and for its basic resource function (A.reroot q).basic. Then
This identity underpins the constructor typing rule and the potential-preservation theorem for the additive constructor shift (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 () evaluates to .
import Definitions.Def_HofmannMoser_Potential universe u
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 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 of the form , where is an arity, is a constructor symbol of arity , and is a -tuple of child values. A tree automaton over consists of:
- a natural number of states , with state space ;
- a designated final (root) state ;
- for each arity and constructor , a finite list of transition rules , where is a -tuple of child states and is the target parent state;
- proofs that has no duplicate entries for every , that only finitely many pairs in have a nonempty rule list , and that at least one pair has a nonempty rule list.
For any tree automaton , value , and state , the run count is defined recursively by filtering to those transitions whose target state equals , mapping each such transition to the left-folded product (starting from ), and summing the resulting products over the filtered list. The basic function of evaluated at is . For any state , the rerooted automaton is identical to (same state count and transition rules) except that its designated final state is set to .
Given any tree automaton , any arity , any constructor symbol , any -tuple of values , and any state , this theorem asserts the equality in :
where the product over is computed by a left fold of multiplication starting from over the list of values , and the sum is taken in list order over the transitions in whose second component equals .
Edge and degenerate cases:
- The state count cannot be , because (and ) inhabit .
- When (so is a nullary leaf constructor and is the empty tuple), the inner left-folded product over the empty list evaluates to , so each transition contributes to the sum.
- When contains no transition with target state , the filtered list is empty and both sides equal .
- If is empty, the inductive type is uninhabited; in that case, for no tuple exists and for no constructor exists, making the quantification vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.