A Rewriting of Fife's Theorem about Overlap-free Words

J. Berstel

IBP-Litp 1994/61: Rapport de Recherche Litp / Litp research reports
11 pages - Octobre/October 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: A Rewriting of Fife's Theorem about Overlap-free Words

Résumé : Le but de cet article de synthèse est de présenter une preuve autonome d'un celèbre théorème de Fife qui donne une caractérisation complète des mots infinis sans chevauchement sur un alphabet binaire. La caractérisation consiste en une paramétrisation de ces mots infinis par un ensemble de mots infinis sur un alphabet ternaire. Le résultat est que cet ensemble est rationnel. La preuve est par la construction explicite de l'automate minimal, obtenu par la méthode des quotients gauches

Abstract : The purpose of this expository paper is to present a self-contained proof of a famous theorem of Fife that gives a full description of the set of infinite overlap-free words over a binary alphabet. Fife's characterization consists in a parametrization of these infinite words by a set of infinite words over a ternary alphabet. The result is that the latter is a regular set. The proof is by the explicit construction of the minimal automaton, obtained by the method of left quotients.

Publications internes Litp 1994 / Litp research reports 1994