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_n), we define an intrinsic sequence e=(e_i){i\ge1} through the triangular valuation identities [ H{n+1}-1=\sum_{i=1}^{n} e_i H_{n+1-i}. ] We prove that this intrinsic sequence coincides with the periodic maximal boundary sequence associated with any coefficient presentation of (H_n). This yields an exact classification of equivalent presentations: a positive integer r is the order of a coefficient presentation if and only if r is a period of e, and the corresponding presentation is uniquely [ (e_1,\ldots,e_{r-1},e_r+1). ] In particular, the canonical reduction is recovered from the primitive period of e. The main structural consequence is language invariance. Although equivalent coefficient presentations generally define different recursive legality grammars and may have different breakpoint decompositions, we prove that they generate exactly the same language of legal representations. Every equivalent presentation is an iterated lift of the canonical reduction, and a general lift-invariance theorem shows that these lifts preserve the accepted language. Thus the place-value sequence determines the intrinsic boundary sequence, the complete family of equivalent coefficient presentations, the canonical reduction, and the associated legality language. The paper also resolves the boundary-to-canonical-reduction reconstruction question arising from the preceding carry-theoretic analysis.
Authors
- Paul Higham
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-08-27
- DOI
- https://doi.org/10.5281/zenodo.22125023
- Primary Topic
- semigroups and automata theory
- Type
- preprint