УДК 519.765

О словах, избегающих квадратов с одной возможной ошибкой замещения / Н. В. Котляров. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 1. С. 48-52.

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

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

Табл. 3. Библиогр. 6.