Алгоритмические проблемы HDOLL-систем, комбинаторика слов и теоремы типа теоремы Вершика-Лившица

В 2007 году автор вместе со своим учеником А.Л.Чернятьевым дал комбинаторный критерий в терминах графов Рози того, что почти периодическое (по другой терминологии, равномерно рекуррентное) сверхслово получается из перекладывания отрезков. Чуть позже для класса почти периодических слов, удовлетворяющих условию idoc condition, другой критерий был получен S.Ferenczi и L.Zamboni.
В этой связи возник вопрос о переводе свойства почти периодического сверхслова быть подстановочным на язык графов Рози. Автор вместе со своим учеником И.В.Митрофановым ввел понятие “схемы Рози” и показал, что подстановочность системы равносильна периодичности схемы Рози. (Граф Рози для $W$ – это семейство графов $\Gamma_n$, отвечающих подсловам длины $n$ сверхслова $W$, стрелкам отвечают подслова длины $n+1$, стрелка соединяет подслово, отвечающее ее началу, с подсловом, отвечающим ее концу. Схема Рози получается путем объединения системы вершин входящей и исходящей степени 1.)
Эта теорема о периодичности является серией теорем типа теоремы Вершика-Лившица. Она позволила установить алгоритмическую разрешимость ряда задач, поставленных А.Л.Семеновым, в частности проблемы проверки почти периодичности для подстановочной системы и проблемы заключительной периодичности.
Обнаружилась связь теорем типа теоремы Вершика-Лившица с проблемой Кете https://en.wikipedia.org/wiki/Köthe_conjecture (в процессе работы с И.Рипсом и Ц.Селлой) и гипотезой Пюизо.