Intrinsic Boundary Sequences, Canonical Presentations, and Language Invariance in Canonical Positive Linear Recurrence Numeration
Canonical positive linear recurrence numeration systems may admit multiple coefficient presentations that generate the same place-value sequence. For every place-value sequence (Hₙ), we define an infinite sequence e = (eᵢ)ᵢ≥1 through the triangular valuation identity Hₙ₊₁ − 1 = ∑ᵢ₌₁ⁿ eᵢHₙ₊₁₋ᵢ. We prove that every coefficient presentation generating (Hₙ) is uniquely determined by a period of this intrinsic sequence, while the canonical reduction is recovered by taking its primitive period. This resolves the reconstruction problem posed in Paper II. The identification also yields a complete classification of coefficient presentations: every period of the intrinsic sequence gives a valid presentation, and every valid presentation arises in this way. Thus, the periods of e are in exact bijection with the presentations generating (Hₙ). We then establish a general lift-invariance theorem showing that every iterated lift of the canonical reduction generates exactly the same legality language. Consequently, any two coefficient presentations producing the same place-value sequence define identical languages of legal representations. Although their recursive legality decompositions may differ, their accepted languages coincide. The trilogy therefore culminates in a complete hierarchy of intrinsic structure: the coefficient vector, maximal boundary word, and legality language are all determined by the place-value sequence itself.
Authors
- Paul Higham
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-08-27
- DOI
- https://doi.org/10.5281/zenodo.22125208
- Primary Topic
- semigroups and automata theory
- Type
- preprint