Canonical Zeckendorf Normalization and sharp iteration depth of the Berstel Adder
RAIRO - Theoretical Informatics and Applications · 2026 · 60 · 29
DOI: 10.1051/ita/2026032 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Theoretical Informatics and Applications, online erschienen am 13.08.2026. Verfasst von Haobo Ma und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We study the canonical normalization map behind Zeckendorf addition: a finite word over {0,1, 2} is replaced by the unique admissible Zeckendorf word with the same Fibonacci value. We first present this map as the canonical normalization induced by a section of the Fibonacci congruence on finite-support digit-count sequences and give a terminating local rewrite presentation whose terminal irreducible word is independent of the rewrite strategy. The main results give exact least-significant-digit-first (LSDF) noncausality invariants for this canonical map. For every output coordinate j , the LSDF anticipation horizon is infinite, even after restricting the domain to genuine digitwise sums of two admissible Zeckendorf inputs: A { 0,1,2 }(ℕ) ( j ) = A Add 2 ( j ) = ∞. The map has no continuous extension at the natural alternating one-sided limit tails. For LSDF finite words, the online commitment deficit is maximal: B ( n ) = n ; equivalently, the prefix-destruction index – the largest number of initial normalized-output digits that may be invalidated by extending an input – satisfies Δ( n ) = n . The same maximal prefix erasure holds on the genuine addition image, Δ Add 2 ( n ) = n , and the input-scale reduced residual complexity satisfies R in ( n ) ≥ n . Non-subsequentiality – that is, impossibility of realization by a deterministic one-pass finite transducer with bounded terminal output – is then a corollary of these sharper quantitative obstructions. These statements are specific to the canonical greedy Zeckendorf normalizer in the LSDF one-sided model and are not claims of a new general normalization theory for Fibonacci or confluent numeration systems. We contrast them with the classical most-significant-digit-first Berstel adder. The existence and ten-state presentation of that adder are classical. We clarify its output-delay quotient: the ten displayed complete-output residuals are distinct as a raw letter-to-letter kernel, but standard subsequential output-delay normalization gives a six-state quotient. We then study the operation of iterating the Berstel recoding until the greedy Zeckendorf normal form is reached. Binary cleanup has exact worst-case depth ⌊ L/2 ⌋ on trimmed binary words of length L , and on genuine addition inputs the sharp depth is max w∈Add 2 MSD (n) τ(w) = ⌈ n /2 ⌉; the maximum is already attained at significant length, without leading-zero padding. A standard local-propagation obstruction is recorded separately in an appendix.
Zitieren
APA
Ma, H., & Zhang, W. (2026). Canonical Zeckendorf Normalization and sharp iteration depth of the Berstel Adder. RAIRO - Theoretical Informatics and Applications, 60, 29. https://doi.org/10.1051/ita/2026032
Vancouver
Ma H, Zhang W. Canonical Zeckendorf Normalization and sharp iteration depth of the Berstel Adder. RAIRO - Theoretical Informatics and Applications. 2026;60:29. doi:10.1051/ita/2026032
BibTeX
@article{Ma2026,
author = {Ma, Haobo and Zhang, Wenlin},
title = {Canonical Zeckendorf Normalization and sharp iteration depth of the Berstel Adder},
journal = {RAIRO - Theoretical Informatics and Applications},
year = {2026},
volume = {60},
pages = {29},
doi = {10.1051/ita/2026032}
}
EUVIMED