AVOIDABLE PATTERNS IN STRINGS OF SYMBOLS

A word is just a finite string of letters. The word W avoids the word U provided no substitution instance of U is a subword of W. W is avoidable if on some finite alphabet there is an infinite collection of words each of which avoids W. W is K th power-free if W avoids x, where x is a letter. We develope the theory of those endomorphisms of free semigroups which preserve K th power-freeness and employ this theory to investigate Kth power-free words. We go on to prove that every Kth power-free word on n letters is a subword of a maximal word of the same kind. Next we examine avoidable words in general and prove that all words of length at least 2non an alphabet with n letters are simultaneously avoidable. We show that on any finite alphabet the collection of avoidable words is simultaneously avoidable. We provide an effective (recursive) characterization of avoidability. Finally we show how our work can be extended to infinite words, to n-dimensional arrays, and to circular words. We give an application to the Burnside problem for semigroups. The present work is chiefly concerned with certain combinatorial properties of strings of symbols. As such, it belongs to formal linguistics, to the theory of free semigroups, and to the theory of partitioned linear orders. While we have taken all of these points of view in the body of this work, it has proven most convenient to base our exposition on an attitude between linguistics and free semigroups. © 1979, University of California, Berkeley. All Rights Reserved.