Prefixes of the Fibonacci word

MaRDI QIDQ6425943zbMATH OpenFDO

Authors Jeffrey Shallit

Publication date 9 February 2023

Abstract: Mignosi, Restivo, and Salemi (1998) proved that for all $epsilon>0$ there exists an integer $N$ such that all prefixes of the Fibonacci word of length $geqN$ contain a suffix of exponent $alph{a}^2-epsilon$, where $alpha=(1+sqrt5)/2$ is the golden ratio. In this note we show how to prove an explicit version of this theorem with tools from automata theory and logic. Along the way we gain a better understanding of the repetitive structure of the Fibonacci word.

This page was built for publication: Prefixes of the Fibonacci word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6425943)