Fife's Theorem Revisited

2011/02/18 by Jeffrey Shallit, Shallit, Jeffrey · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.1102.3932

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.

Cited by

• Low complexity binary words avoiding (5/2)⁺-powers

Related

• Binary words containing infinitely many overlaps
• A new upper bound for separating words
• The analogue of overlap-freeness for the period-doubling sequence
• A Sharper Upper Bound for the Separating Words Problem
• Don's conjecture for binary completely reachable automata: an approach and its limitations