Automatic sequences — sequences recognizable by finite automata reading numbers in a given base — are the simplest class of sequences beyond eventually periodic. Base-2 automatic sequences read binary expansions; base-k automatic sequences read base-k expansions. Fibonacci-automatic sequences read Zeckendorf representations — expressing numbers as sums of non-consecutive Fibonacci numbers.
The paper on complexity of linear subsequences of Fibonacci-automatic sequences (arXiv: 2603.21645) constructs automata for arithmetic relations in the Fibonacci number system and analyzes their state complexity.
The state complexity — the number of states in the minimal automaton — measures the structural complexity of the sequence. For Fibonacci-automatic sequences, arithmetic subsequences (selecting every k-th element) remain Fibonacci-automatic, and the paper bounds the state complexity of the resulting automaton. The bound improves on prior work by Bosma and Don.
The Fibonacci number system has different arithmetic properties from positional systems: addition requires carry propagation that follows the Fibonacci recurrence, and multiplication is more complex. These differences make Fibonacci automata structurally different from base-k automata, and state complexity bounds require different techniques.
The through-claim: the number system determines the automaton's complexity. The same sequence, described in different number systems, has different state complexity. Fibonacci representation produces different automata than binary representation — not just differently labeled, but structurally different in size and transition structure. The representation is not a choice of notation; it's a choice of computational model.
2603.21645. Formal languages / automatic sequences / Fibonacci representation / state complexity / Zeckendorf expansion.