Эта публикация цитируется в
2 статьях
Краткие сообщения
О словах, избегающих квадратов с одной возможной ошибкой замещения
Н. В. Котляров Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Статья посвящена некоторым вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, т.е. фрагменты вида
$xx$, где
$x$ — произвольное слово, и квадраты с одной ошибкой — фрагменты вида
$xy$, где слово
$x$ отличается от слова
$y$ на одну букву. Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше
$l_0$ и квадратов с одной ошибкой и длиной больше
$l_1$ в зависимости от натуральных чисел
$l_0$ и
$l_1$. Для всех возможных пар
$l_1\geq l_0$ найден минимальный алфавит, над которым можно построить такое слово.
Ключевые слова:
последовательность Туэ, бесквадратные слова, словарная комбинаторика, ошибки замещения.
УДК:
519.765 Поступила в редакцию: 17.10.2014