Petrov, A. N. Sequence avoiding any complete word. (English. Russian original) Zbl 0677.20055 Math. Notes 44, No. 3-4, 764-767 (1988); translation from Mat. Zametki 44, No. 4, 517-522 (1988). A word u is said to avoid a word v is the subwords of the word u there are no instances of the word v. We recall that an instance of the word v is the result of substituting certain words for letters of the word v; also identical letters are replaced by identical words. We will say that a sequence of words \(\{u_ i|\) \(i<\omega \}\) avoids the word v if each word u, avoids v. We call a word complete if it does not contain any letters which occur exactly once, and for any different letters, x, y of this word, the words xy and yx are subwords. In this note we prove the following Theorem: There exists a sequence of words in an alphabet on four letters which avoids every complete word. Cited in 1 Document MSC: 20M35 Semigroups in automata theory, linguistics, etc. 20M05 Free semigroups, generators and relations, word problems Keywords:subwords; instances; sequence of words; alphabet; complete word PDFBibTeX XMLCite \textit{A. N. Petrov}, Math. Notes 44, No. 3--4, 764--767 (1988; Zbl 0677.20055); translation from Mat. Zametki 44, No. 4, 517--522 (1988) Full Text: DOI References: [1] A. I. Zimin, ?Blocking sets of terms,? Mat. Sb.,119, No. 3, 363-375 (1982). [2] D. R. Bean, A. Ehrenfeucht and G. McNulty, ?Avoidable patterns in strings of symbols,? Pac. J.Math.,85, No. 2, 261-294 (1979). · Zbl 0428.05001 [3] S. E. Arshon, ?A proof of the existence of n-valued infinite asymmetric sequences,? Mat. Sb.,2(44), No. 4, 769-779 (1937). [4] A. Thue, ?Über unendliche Zeichenreihen,? Nor. Vid. Selsk. Skr. Ser. I Mat Kl., Christiania, No. 7, 1-22 (1906). · JFM 39.0283.01 [5] S. I. Adyan, Burnside’s Problem and Group Identities [in Russian], Nauka, Moscow (1975). [6] A. A. Evdokimov, ?Strongly asymmetric sequences generated by a finite number of symbols,? Dokl. Akad. Nauk SSSR,179, No. 6, 1268-1271 (1968). · Zbl 0186.01504 [7] P. A. B. Pleasants, ?Nonrepetitive sequences,? Proces. Cambridge Philos. Soc.,68, No. 2, 267-274 (1970). · doi:10.1017/S0305004100046077 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.