Vol. 85, No. 2, 1979

Recent Issues
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Avoidable patterns in strings of symbols

Dwight Richard Bean, Andrzej Ehrenfeucht and George Frank McNulty

Vol. 85 (1979), No. 2, 261–294

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.

Mathematical Subject Classification 2000
Primary: 20M05
Secondary: 20M35, 68F05
Received: 7 February 1978
Revised: 14 June 1979
Published: 1 December 1979
Dwight Richard Bean
Andrzej Ehrenfeucht
George Frank McNulty