Avoiding or limiting regularities in words

Pascal Ochem 1 Michaël Rao 2 Matthieu Rosenfeld 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : It is commonly admitted that the origin of combinatorics on words goes back to the work of Axel Thue in the beginning of the twentieth century, with his results on repetition-free words. Thue showed that one can avoid cubes on infinite binary words and squares on ternary words. Up to now, a large part of the work on the theoretic part of combinatorics on words can be viewed as extensions or variations of Thue’s work, that is, showing the existence (or nonexistence) of infinite words avoiding, or limiting, a repetition-like pattern. The goal of this chapter is to present the state of the art in the domain and also to present general techniques used to prove a positive or a negative result. Given a repetition pattern P and an alphabet, we want to know if an infinite word without P exists. If it exists, we are also interested in the size of the language of words avoiding P, that is, the growth rate of the language. Otherwise, we are interested in the minimum number of factors P that a word must contain. We talk about limitation of usual, fractional, abelian, and k-abelian repetitions and other generalizations such as patterns and formulas. The last sections are dedicated to the presentation of general techniques to prove the existence or the nonexistence of an infinite word with a given property.
Document type :
Book sections
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02083655
Contributor : Pascal Ochem <>
Submitted on : Friday, March 29, 2019 - 10:43:14 AM
Last modification on : Friday, June 21, 2019 - 1:47:07 AM

Identifiers

Citation

Pascal Ochem, Michaël Rao, Matthieu Rosenfeld. Avoiding or limiting regularities in words. Sequences, Groups and Number Theory, pp.177-212, 2018, 978-3-319-69151-0. ⟨10.1007/978-3-319-69152-7_5⟩. ⟨lirmm-02083655⟩

Share

Metrics

Record views

51