RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, номер 1, страницы 48–52 (Mi vmumm122)

Эта публикация цитируется в 2 статьях

Краткие сообщения

О словах, избегающих квадратов с одной возможной ошибкой замещения

Н. В. Котляров

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Статья посвящена некоторым вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, т.е. фрагменты вида $xx$, где $x$ — произвольное слово, и квадраты с одной ошибкой — фрагменты вида $xy$, где слово $x$ отличается от слова $y$ на одну букву. Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше $l_0$ и квадратов с одной ошибкой и длиной больше $l_1$ в зависимости от натуральных чисел $l_0$ и $l_1$. Для всех возможных пар $l_1\geq l_0$ найден минимальный алфавит, над которым можно построить такое слово.

Ключевые слова: последовательность Туэ, бесквадратные слова, словарная комбинаторика, ошибки замещения.

УДК: 519.765

Поступила в редакцию: 17.10.2014


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2016, 71:1, 31–34

Реферативные базы данных:


© МИАН, 2024