Шаблоны, избегаемые антицепями слов, и их алгебраические приложения, Инна Михайлова

Первой работой по комбинаторике слов считается статья Туэ, в которой он показывает, что существует бесконечное слово над трехбуквенным алфавитом, не содержащее двух одинаковых подряд идущих подслов. В современной терминологии говорится об избегаемости квадратов. Комбинаторный подход оказался естественным для решения задач для полугрупп и их многообразий, заданных тождествами вида u=0, и напрямую связан с избегаемостью шаблона u. В данной работе показывается, что такие многообразия обладают свойством решеточной универсальности (их решетка подмногообразий достаточно сложна в том смысле, что в нее вкладывается решетка подмногообразий любых алгебр с не более чем счетным числом операций). Более того, понятие избегаемости можно ввести для тождеств произвольного вида и тогда, как показано в работе, можно классифицировать решеточно универсальные многообразия полугрупп. Основная сложность такого подхода состоит в том, чтобы доказать, что каждый избегаемый шаблон (избегаемое тождество)...