6-апериодические слова над трехбуквенным алфавитом
Автор: Сенашов В.И.
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 т.21, 2020 года.
Бесплатный доступ
Работа посвящена изучению множеств апериодических слов над конечным алфавитом. Множество таких слов можно рассматривать как некоторый конечный формальный язык. У. Бернсайд задал вопрос о локальной конечности периодических групп. Отрицательный ответ был получен лишь через шестьдесят лет Е. С. Голодом. Вскоре С. В. Алешиным, Р. И. Григорчуком, В. И. Сущанским были построены еще примеры, подтверждающие отрицательный ответ на вопрос Бернсайда. Конечность свободной бернсайдовской группы периода n установлена в разное время для периодов два и три (У. Бернсайд), для периода четыре (У. Бернсайд; И. Н. Санов), для периода шесть (М. Холл). Бесконечность такой группы, для нечетных показателей, превышающих 4381, установлена в работе П. С. Новикова - С. И. Адяна (1967), а для нечетных показателей, превышающих 664, - в монографии С. И. Адяна (1975). Геометрический метод доказательства для нечетных показателей, превышающих 1010, принадлежит А. Ю. Ольшанскому (1989). В данной статье рассматриваем множество 6-апериодических слов. l-апериодическим словом называется слово Х, не содержащее нетривиальных подслов типа Yl. В книге С. И. Адяна (1975) имеется обоснование С. Е. Аршона (1937) того, что в двухбуквенном алфавите имеется бесконечно много три-апериодических слов любой длины. В книге А. Ю. Ольшанского (1989) приведено доказательство бесконечности множества шесть-апериодических слов и получена оценка количества таких слов любой данной длины. Здесь мы хотим оценить функцию количества шесть-апериодических слов любой данной длины в алфавите из трех букв. Полученные результаты могут быть полезны при кодировании информации в сеансах космосвязи.
Локально конечная группа, слово, апериодичность, оценка, формальный язык
Короткий адрес: https://sciup.org/148321981
IDR: 148321981 | DOI: 10.31772/2587-6066-2020-21-3-333-336
Список литературы 6-апериодические слова над трехбуквенным алфавитом
- Burnside W. [On an unsettled question in the theory of discontinuous groups]. Quart. J. Pure. Appl. Math. 1902, Vol. 33, P. 230-238.
- Novikov P. S., Adyan S. I. [On infinite periodic groups]. Izv. AN SSSR, Ser. mat. 1968, No. 1 (32), P. 212-244 (In Russ.).
- Novikov P. S., Adyan S. I. [On infinite periodic groups. II]. Izv. AN SSSR, Ser. mat. 1968, No. 2 (32), P. 251-524 (In Russ.).
- Novikov P. S., Adyan S. I. [On infinite periodic groups. III]. Izv. AN SSSR, Ser. mat. 1968, No. 3 (32), P. 709-731 (In Russ.).
- Adyan S. I. Problema Bernsayda i tozhdestva v gruppakh [The Burnside Problem and Identities in Groups]. Moscow, Nauka Publ., 1975, 336 p.
- Adyan S. I. [Burnside's problem and related questions]. Uspekhi Mat. sciences. 2010. Vol. 65, Issue. 5 (395), P. 5-60 (In Russ.).
- Thue A. Uber unendliche Zeichenreih. Norcke Vid. Selsk. skr., I Mat. Nat. Kl. Christiania. 1906. Bd. 7. P. 1-22.
- Arshon S. E. [Proof of existence of n -unit infinite asymmetric sequences]. Mat. sb. 1937, No. 4(2 (44)), P. 769-779 (In Russ.).
- Olshansky A. Yu. Geometriya opredelyayushchikh sootnosheniy v gruppakh [Geometry of defining relations in groups]. Moscow, Nauka Publ., 1989. 448 p.
- Senashov V. I. [Aperiodic words]. Reshetnevskiye chteniya: materialy XIX Mezhdunar. nauch.-prakt. konf., posvyashch. 55-letiyu Sib. gos. aerokosmich. un-ta im. akad. M. F. Reshetneva [Reshetnev Readings: materials of XIX Intern. scientific and practical. conf. for 55th anniversary of Sib. State. Aerokosmich. Univ. Acad. M. F. Reshetnev] (10-14 Nov. 2015, Krasnoyarsk). Krasnoyarsk, 2015, part 2, P. 132-133 (In Russ.).
- Senashov V. I. [Improved estimates of the number 6-aperiodic words of fixed length]. Vestnik SibGAU. 2016, Vol. 17, No. 2, P. 168-172 (In Russ.).
- Senashov V. I. [Estimation of the number of 5-aperiodic words]. Vestnik Tuvinskogo gos. un-ta. Tekhn. ifiz.-mat. nauki. 2017, No. 3, P. 132-138 (In Russ.).
- Senashov V. I. [Estimation of the number of 12-aperiodic words of fixed length]. Vestnik SibGAU. 2017, Vol. 18, No. 1, P. 93-96 (In Russ.).
