×

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.

MSC:

20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
PDFBibTeX XMLCite
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.