Avoidable patterns and regularities in words

Abstract

In this thesis, we study the avoidability of patterns on a fixed alphabet, and other regularities in words, avoidable or unavoidable. Specifically, we give a complete classification of binary patterns and a partial classification of ternary patterns; moreover, we prove that there are always finitely many unavoidable patterns on a given alphabet with a given number of variables. We introduce DOL-avoidability and HDOL-avoidability, which reflect the link between pattern avoidability and L-systems, and we show that it is possible, with a few restrictions, to decide whether a HDOL-language avoids a pattern. We also consider two more combinatorial problems, namely counting words avoiding a pattern, in the special case of overlaps, and constructing sequences with a given subword complexity.

Keywords

Language theory, Combinatorics, Word, Avoidable pattern, Decidability, L-system, Overlap, Subword complexity, Regular sequence, Special factor.
English Franšais Previous Next Up Feedback
JC 1994-07-07