Generating Fibonacci Words via the Prefix--Suffix Duplication Operation
2026-07-22 • Formal Languages and Automata Theory
Formal Languages and Automata TheoryDiscrete Mathematics
AI summaryⓘ
The authors study how special sequences of letters called Fibonacci words can be made from each other using a process that copies parts of the word and attaches them in front. They focus on a particular operation called prefix duplication with a limit on how much can be copied at once. The authors prove that any even- or odd-indexed Fibonacci word can be generated from another of the same parity using prefix duplications that copy at most three letters, and they show that copying fewer than three letters won't always work. They also provide an efficient method to find the exact steps to create one word from another.
Fibonacci wordscombinatorics on wordsprefix duplicationsuffix duplicationlocal rewritinginfinite wordsbounded duplication lengthThue–Morse wordperiod-doubling wordalgorithm complexity
Authors
Diego Cabrera Salamanca, Taylor J. Smith
Abstract
The finite and infinite Fibonacci words are classical objects in combinatorics on words. Bio-inspired language operations provide a useful tool for studying how finite and infinite words can arise via local rewriting mechanisms. For example, the suffix square completion operation is known to generate the infinite Fibonacci word, as well as other infinite words such as the Thue--Morse word and the period-doubling word. The prefix--suffix duplication operation produces a language of words formed by appending prefixes or suffixes of a word $w$ to the front or back of $w$ respectively, and Dumitran conjectured that Fibonacci words of the same index parity can be generated from one another by the bounded duplication length variant of this operation. In this paper, we resolve and strengthen Dumitran's conjecture. We show that, for all $1 \leq p \leq n$, it is possible to generate the Fibonacci word $F_{2n}$ from $F_{2p}$, and $F_{2n+1}$ from $F_{2p+1}$, using only prefix duplications with a bound of $k \geq 3$. We furthermore show that this bound of $3$ is optimal, and we give an algorithm that produces a witness derivation in time linear in the length of the target Fibonacci word.