Vol. 85, No. 2, 1979

Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
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
Abstract

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
Milestones
Received: 7 February 1978
Revised: 14 June 1979
Published: 1 December 1979
Authors
Dwight Richard Bean
Andrzej Ehrenfeucht
George Frank McNulty