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

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, номер 3, страницы 8–16 (Mi vmumm27)

Математика

О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения

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

ОАО "Яндекс", г. Москва

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

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

УДК: 519.765

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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2018, 73:3, 90–97

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


© МИАН, 2024