Recursion-tree unfolding of a decreasing specification
DefinitionCallCountPOPBR_Supplement_DecSpec_unfoldgraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1recursive-algorithms
The unfolding of a decreasing-argument specification at input is the labelled ordered tree with root label and, in the specification's call order, the unfoldings at all immediate child inputs.
Decreasing child labels make this a finite tree. Repeated immediate calls produce repeated child subtrees.
Definition code
import Definitions.Def_CallCountPOPBR_Supplement_DecSpec import Definitions.Def_CallCountPOPBR_Supplement_LTree set_option autoImplicit false namespace CallCountPOPBR.Supplement /-- **The recursion tree generated by a specification** (§5, §5.2). Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), §5, p.9: "Let T_n be the rooted recursion tree generated on input n"; §5.2, p.10, Theorem 5.5: "generated by a deterministic decreasing-argument recursive specification". `unfold s n` has root label `n` and, in order, one child subtree `unfold s k` for each immediate call `R(k)` in `s.calls n`. **Formalization Note.** A `DecSpec` is deterministic: `R(n)` always makes the same ordered list of calls, so every call to `R(k)` unfolds to the same tree. -/ def DecSpec.unfold (s : DecSpec) (n : ℕ) : LTree := .node n ((s.calls n).attach.map (fun k => s.unfold k.1)) termination_by n decreasing_by exact s.dec n k.1 k.2 end CallCountPOPBR.Supplement
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884…), Section 5 and Theorem 5.5, pp.9–10