m-aperiodic words on three-letter alphabet
Автор: Senashov V.I.
Журнал: Siberian Aerospace Journal @vestnik-sibsau-en
Рубрика: Informatics, computer technology and management
Статья в выпуске: 2 vol.25, 2024 года.
Бесплатный доступ
The work is devoted to the study of sets of aperiodic words over a finite alphabet. The set of aperiodic words can be considered as a dictionary of some finite formal language. The existence of infinite words in two-letter or three-letter alphabets that do not contain subwords that are third powers or, respectively, squares of other words was first discovered more than a hundred years ago. S.I. Adyan in 2010 constructed an example of an infinite sequence of irreducible words, each of which is the beginning of the next and does not contain word squares in a two-letter alphabet. S.E. Arshon established the existence of an n-digit asymmetric repetition-free sequence for an alphabet of at least three letters. In the monograph by S.I. Adyan proved that in an alphabet of two symbols there exist infinite 3-aperiodic sequences. In the works of other authors, generalizations of aperiodicity were considered, when not only the powers of some subwords were excluded. In the monograph by A.Yu. Olshansky proved the infinity of the set of 6-aperiodic words in a two-letter alphabet and obtained an estimate for the number of such words of any given length. The author previously considered the case of a three-letter alphabet only in the case of 6-aperiodic words. In this article, we prove the infinity of the set of m-aperiodic words in the three-letter alphabet at m 4 and obtain an estimate for the set of such words. The results can be applied when encoding information in space communications.
Alphabet, non-repetitive sequence, word, aperiodicity, estimate, formal language
Короткий адрес: https://sciup.org/148329733
IDR: 148329733 | DOI: 10.31772/2712-8970-2024-25-2-176-181
Список литературы m-aperiodic words on three-letter alphabet
- Thue A. Uber unendliche Zeichenreih. Norcke Vid. Selsk. skr., I Mat. Nat. Kl. Christiania. 1906, bd. 7, p. 1–22.
- Adyan S. I. [Burnside's problem and related questions]. Uspekhi Mat. sciences. 2010, Vol. 65, Is. 5 (395), P. 5–60. (In Russ.)
- Arshon S. E. [Proof of existence of n-unit infinite asymmetric sequences]. Mat. sb. 1937, No. 4 (2 (44)), P. 769–779. (In Russ.)
- Adyan S. I. Problema Bernsayda i tozhdestva v gruppakh [Bernside Problem and Identities in Groups]. Moscow, Nauka Publ., 1975, 336 p.
- Novikov P. S., Adyan S. I. [On infinite periodic groups. I]. Izv. USSR Academy of Sciences, ser. math. 1967, No. 1 (32), P. 212–244. (In Russ.)
- Novikov P. S., Adyan S. I. [On infinite periodic groups II]. Izv. USSR Academy of Sciences, ser. math. 1967, No. 2 (32), P. 251–524. (In Russ.)
- Novikov P. S., Adyan S. I. [On infinite periodic groups III]. Izv. USSR Academy of Sciences, ser. math. 1967, No. 3 (32), P. 708–731. (In Russ.)
- Shur A. M. [Structure of the set of cubeless Z-words in a two-letter alphabet]. Izv. RAS. Ser. Mat. 2000, Vol. 64, Is. 4, P. 201–224. (In Russ.)
- Shur A. M. Overlap-free words and Thue-Morse sequences. Int. J. Alg. and et al. 1996. Vol. 6. P. 353–367.
- Shur A. M. Binary words avoided by the Thue-Morse sequence. Semigroup Forum. 1996. Vol. 53. P. 212–219.
- Olshansky A. Yu. Geometriya opredelyayushchikh sootnosheniy v gruppakh [Geometry of defining relations in groups]. Moscow, Nauka Publ., 1989, 448 p.
- Senashov V. I. [Improved estimates of the number 6-aperiodic words of fixed length]. Vestnik SibGAU. 2016, No. 2 (17), P. 168–172 (In Russ.).
- Senashov V. I. [Aperiodic words]. Reshetnevskiye chteniya. 2015, Vol. 2, No. 19, P. 132–133. (In Russ.)
- Senashov V. I. [Estimation of the number of aperiodic words]. Siberian Aerospace Journal. 2022. No. 3 (23), P. 409–416. (In Russ.)
- Senashov V. I. [6-aperiodic words over the three-letter alphabet]. Siberian Journal of Science and Technology. 2020, No. 3 (21), P. 333–336. (In Russ.)
- Bean D. R., Ehrenfeucht A., McNulty G. F. Avoidable patterns in strings of symbols. Pacific J. Math. 1979, No. 2 (85), P. 261–295.
