|
Вестник Московского университета. Серия 1: Математика. Механика, 2018, номер 3, страницы 8–16
(Mi vmumm27)
|
|
|
|
Математика
О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения
Н. В. Котляров ОАО "Яндекс", г. Москва
Аннотация:
Работа посвящена вопросам, связанным с существованием периодических структур в словах из формальных языков. В качестве периодических структур рассматриваются квадраты, т.е. фрагменты вида $xx$, где $x$ — произвольное слово, и $\Delta$-квадраты, т.е. фрагменты вида $xy$, где слово $x$ отличается от слова $y$ не более чем на $\Delta$ букв. Показано существование сколь угодно длинных слов над трехбуквенным алфавитом, не содержащих $\Delta$-квадратов с периодом больше $\Delta$. В частности, указан способ построения таких слов для любого $\Delta$.
Ключевые слова:
последовательность Туэ, бесквадратные слова, словарная комбинаторика, ошибки замещения.
Поступила в редакцию: 13.09.2017
Образец цитирования:
Н. В. Котляров, “О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, № 3, 8–16; Moscow University Mathematics Bulletin, 73:3 (2018), 90–97
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm27 https://www.mathnet.ru/rus/vmumm/y2018/i3/p8
|
Статистика просмотров: |
Страница аннотации: | 150 | PDF полного текста: | 27 | Список литературы: | 30 | Первая страница: | 4 |
|