О равномерно рекуррентных словах, порождаемых перекладыванием отрезков, в том числе с изменением ориентации

Работа посвящена обзору некоторых задач символическиой динамики. Дается описание равномерно рекуррентных слов связанных с перекладыванием отрезков. Ответ получен в терминах эволюции размеченных графов Рози слова $W$. $k$-граф Рози слова $W$ – это ориентированный граф, вершины которого взаимнооднозначно соответствуют подсловам длины $k$ слова $W$, из вершины $A$ в вершину $B$ ведет стрелка, если в $W$ есть подслово длины $k+1$, у которого первые $k$ символов – подслово соответствующее $A$, последние $k$ символов – подслово, соответствующее $B$. Последователем ориентированного $k$-графа $G$ называется ориентированный граф $\mathrm{Fol}(G)$ построенный следующим образом: вершины графа $G$ биективно соответствуют ребрам графа $G$, из вершины $A$ в вершину $B$ ведет стрелка, если в графе $G$ конечная вершина ребра $A$ является начальной вершиной ребра $B$. $(k+1)$-граф является подграфом последователя $k$-графа и получается из него удалением некоторых ребер. Вешины, из которых выходит (или в которые входят) более одного ребра, соответсвуют специальным подсловам (см. гл.2), вершины, в которые входят и выходят более одного ребра, соответствуют биспециальным подсловам. Последовательность $k$-графов Рози составляет эволюцию графов Рози слова $W$. Граф Рози называется размеченным, если его ребра помечены буквами $l$ и $r$, а некоторые вершины (возможно, ни одна) помечены символом “–”.
Последователем размеченного графа Рози назовем ориентированный граф, являющийся его последователем как графа Рози, разметка ребер которого определяется по правилу:

• Ребра, входящие в развилку должны быть помечены теми же символами, как и ребра, входящие в любого левого потомка этой вершины;
• Ребра, выходящие из развилки должны быть помечены теми же символами, как и ребра, выходящие из любого правого потомка этой вершины;
• Если вершина помечена знаком “–”, то все ее правые потомки также должны быть помечены знаком “–”.

В терминах размеченных графов Рози определяется асимптотически правильная эволюция графов Рози, то есть определяются правила перехода от $k$-графов к $(k+1)$-графам. Именно, эволюция называется правильной, если для всех $k\geq 1$ выполняются следующие условия при переходе от $k$-графа $G_k$ к $(k+1)$-графу $G_{k+1}$ :

• Валентность любой вершины не более $2$,то есть в нее входит и выходит не более $2$-х ребер.
• Если в графе нет вершин, соответсвующих биспециальным подсловам, то $G_{n+1}$ совпадает с последователем $D(G_n)$;
• Если вершина, соответствующая биспециальному слову не помечена знаком “–”, то ребра, соответствующие запрещенным словам выбираются из пар $lr$ и $rl$
• Если вершина помечена знаком “–”, то удаляемые ребра должны выбираться из пары $ll$ или $rr$.

Эволюция называется асимптотически правильной, если это условие выполняется для всех $k$ начиная с какого-то $k=K$. Ориентированная эволюция графов подразумевает отсутствие вершин, помеченных знаком “–”. Основная теорема данной работы заключается в описании сверхслов, связанных с перекладыванием отрезков: Теорема. Равномерно-рекуррентное слово $W$

• Порождается перекладыванием отрезков, тогда и только тогда, когда слово обеспечивается асимптотически правильной эволюцией размеченных графов Рози.
• Порождается перекладыванием отрезков с сохранением ориентации тогда и только тогда, когда слово обеспечивается асимптотически правильной ориентированной эволюцией размеченных графов Рози.