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.
JC 1994-07-07