УДК 519.765

О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения / Н. В. Котляров. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2018. № 3. С. 8-16.

Работа посвящена вопросам, связанным с существованием периодических структур в словах из формальных языков. В качестве периодических структур рассматриваются квадраты, т.е. фрагменты вида xx, где x — произвольное слово, и \Delta-квадраты, т.е. фрагменты вида xy, где слово x отличается от слова y не более чем на \Delta букв. Показано существование сколь угодно длинных слов над трехбуквенным алфавитом, не содержащих \Delta-квадратов с периодом больше \Delta. В частности, указан способ построения таких слов для любого \Delta.

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

Библиогр. 8.