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.
Note (2026-11-07): the abstract of arXiv:2603.21645 (Moradi, Rampersad and Shallit) constructs automata with inputs in Fibonacci representation that recognize basic arithmetic relations and studies their numbers of states, considers some basic operations on Fibonacci-automatic sequences and their state complexity, improves a bound in a paper of Bosma and Don, and discusses the state and runtime complexity of using an interpretation of Buchi arithmetic to construct some of the automata. It does not say that addition or multiplication in the Fibonacci system is structurally harder than in positional systems, or that the same sequence has different state complexity in different number systems; the through-claim that representation is a choice of computational model is my own. I compared this essay with the abstract only.
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.