Тип публикации: статья из журнала
Год издания: 2024
Идентификатор DOI: 10.31772/2712-8970-2024-25-2-176-181
Ключевые слова: alphabet, Non-repetitive sequence, word, aperiodicity, estimate, formal language, алфавит, бесповторная последовательность, слово, апериодичность, оценка, формальный язык
Аннотация: 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. Работа посвящена изучению множеств апериодических слов над конечным алфавитом. Множество апериодических слов можно рассматривать как словарь некоторого конечного формального языка. Существование бесконечных слов в двухбуквенном или трехбуквенном алфавитах, которые не содержат подслов, являющихся третьими степенями или, соответственно, квадратами других слов, впервые получены более ста лет назад. С. И. Адян в 2010 г. построил пример бесконечной последовательности несократимых слов, каждое из которых является началом следующего и не содержит квадратов слов в алфавите из двух букв. С. Е. Аршон установил существование n-значной ассиметричной бесповторной последовательности для алфавита не менее чем из трех букв. В монографии С. И. Адяна доказано, что в алфавите из двух символов существуют бесконечные 3-апериодические последовательности. В работах других авторов рассматривались обобщения апериодичности, когда исключались не только степени некоторых подслов. В монографии А. Ю. Ольшанского доказана бесконечность множества 6-апериодических слов в двухбуквенном алфавите и получена оценка количества таких слов любой данной длины. Автором ранее случай трехбуквенного алфавита рассмотрен только в случае 6-апериодических слов. В данной статье доказана бесконечность множества m-апериодических слов в трехбуквенном алфавите при m ³ 4 и получена оценка множества таких слов. Полученные результаты могут быть полезны при кодировании информации в сеансах космической связи.
Журнал: Сибирский аэрокосмический журнал
Выпуск журнала: Т. 25, № 2
Номера страниц: 176-181
ISSN журнала: 27128970
Место издания: Красноярск
Издатель: Сибирский государственный университет науки и технологий им. акад. М.Ф. Решетнева