Ученые записки математических кафедр вып. 1970 г.

соотношение. Будем говорить, что при Х А ; У — ’’ Х В ^ У буквы слов , Вь затрагиваются при данном элементарном преобразовании, а буквы слов X , У не затрагиваются. Существование алгоритма, решающего проблему тождества для полугруппы П о условиями а, б, следует из теоремы I . ТЕОРЕМА I . Для двух равных в П слов Ы и V найдется последовательность ( 2 .1 ) , в которой I (тк)< г пи»* ¿ ( е л щ и . ) + 1 (у)] , Действительно, последовательность (2 .1 ) всегда можно пред­ ставить состоящей из различных слов и поскольку длина ее слов ограничена известным числом, то тем самым ограничено и число слов этой последовательности при данных IX ) ]/ § 3 . С е т ь Сеть последовательности элементарных преобразований (2 .1 ) определим через следующее построение. . Две различные точки /вершины/ плоскости Р и 0. соединим < простыми дугами %, 1Х А, . . , , Хщ , ориентируя их о т Рк 0 (Рис. I). . Если 7^ - V .» то дугу разбиваем 5-1 вер шинами на частей /р е б е р / Ч , . придавая каждому % значение ¥ и полагая при этом ПЧ ) ■ * ( % ) * %