Growth properties of power-free languages

Abstract

The aim of this paper is to survey the area formed by the intersection of two popular lines of research in formal language theory. The first line, originated by Thue in 1906, concerns repetition-free words and languages. The second line is the study of growth functions for words and languages; it can be traced back to the classical papers by Morse and Hedlund on symbolic dynamics (1938, 1940). Growth functions of repetition-free languages have been investigated since the 1980's. Most of the results are obtained for power-free languages, but some ideas can be applied for languages avoiding patterns and Abelian-power-free languages as well. In this paper, we present key contributions to the area, its state of the art, and conjectures that suggest answers to some natural unsolved problems. Also, we pay much attention to the tools and techniques that made the progress in the area possible. © 2012 Elsevier Inc.