|
Вестник Московского университета. Серия 1: Математика. Механика, 2016, номер 1, страницы 48–52
(Mi vmumm122)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Краткие сообщения
О словах, избегающих квадратов с одной возможной ошибкой замещения
Н. В. Котляров Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Статья посвящена некоторым вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, т.е. фрагменты вида $xx$, где $x$ — произвольное слово, и квадраты с одной ошибкой — фрагменты вида $xy$, где слово $x$ отличается от слова $y$ на одну букву. Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше $l_0$ и квадратов с одной ошибкой и длиной больше $l_1$ в зависимости от натуральных чисел $l_0$ и $l_1$. Для всех возможных пар $l_1\geq l_0$ найден минимальный алфавит, над которым можно построить такое слово.
Ключевые слова:
последовательность Туэ, бесквадратные слова, словарная комбинаторика, ошибки замещения.
Поступила в редакцию: 17.10.2014
Образец цитирования:
Н. В. Котляров, “О словах, избегающих квадратов с одной возможной ошибкой замещения”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 1, 48–52; Moscow University Mathematics Bulletin, 71:1 (2016), 31–34
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm122 https://www.mathnet.ru/rus/vmumm/y2016/i1/p48
|
Статистика просмотров: |
Страница аннотации: | 151 | PDF полного текста: | 27 | Список литературы: | 40 |
|