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 k-th power-free
words. We go on to prove that every k-th 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 2n on 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.
