Back to Search Start Over

Fife's Theorem Revisited

Authors :
Shallit, Jeffrey
Publication Year :
2011
Publisher :
arXiv, 2011.

Abstract

We give another proof of a theorem of Fife - understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our proof is significantly simpler than those in the literature. As an application we give a complete characterization of the overlap-free words that are 2-automatic.

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....1b255a056bb1e0652e90940d373bfb85
Full Text :
https://doi.org/10.48550/arxiv.1102.3932