Пути на графе как элементы полугруппы

Будем рассматривать слова в конечном алфавите. Допустим, конечное множество слов. объявлены запрещенными, то есть приравнены к нулю. Тогда и все слова, содержащие запрещенные тоже равны нулю. Множество ненулевых слов при этом может оказаться конечным или бесконечным. Не очень сложная олимпиадная задача: Если множество ненулевых слов бесконечно, то существует и бесконечное периодическое слово, не содержащее запрещенных подслов.
Множество слов относительно операции приписывания одного слова к другому является полугруппой. На языке полугрупп утверждение задачи выше означает, что в конечно порожденной (конечный алфавит) конечно представленной (конечное число запрещенных слов) мономиальной (каждое определяющее соотношение вида W=0), бесконечной (множество ненулевых слов бесконечно) полугруппе существует элемент, являющийся ненулевым в любой степени. Пользуясь определением ниль-элемента, то есть слова, некоторая степень которого равна нулю, можно дать эквивалентное определение. Полугруппа называется нильполугруппой, если каждый элемент в некоторой степени равен нулю. Тогда эквивалентная формулировка: любая конечнопорожденная конечно представленная мономиальная нильполугруппа является конечной.
Что же будет, если делать не только запрещенные слова, но и приравнивать некоторые слова друг к другу? Тогда ситуация заметно усложняется, и этот вопрос был поставлен в Свердловской тетради Л.Н.Шевриным и М.В.Сапиром. Оказывается, что в этом случае бесконечную конечно представленную нильполугруппу построить можно. Но для этого пришлось применить дополнительные идеи.
Слова полугруппы интерпретируются как кодировки путей на специально построенном графе. Эквивалентность слов означает эквивалентность путей на графе, то есть возможность перевести один путь в другой локальными заменами. Запрещающие соотношения соответствуют невозможным кодировкам.
Все это приводит к новому подходу к построению алгебраических объектов, который и будем обсуждать в докладе.