АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1990 г.

стороннее, .двустороннее, внутреннее вховдение в определяющие слова, если найдутся определяющие слова соответственно вида: И Х ; Х Е ; W и Я ; F X H , где F , Н непусты. Мы будем рассматривать полугруппы, множество определяющих слов которых удовлетворяет следующим условиям: 1) никакое С/ не является куском; 2 ) если Су s X Y « где X , Y - куски, то либо а) хотя бы один из кусков X , У имеет только односторонние (только правосторонние ши только левосторонние; вхождения; либо б) X не имеет правосторонних и У левосторон­ них вхождений. . Пусть в полугруппе П U .- V . Тогда существует п. э. п. гс » Т 0 - г , - . . . — Tm = V . (а) Определим понятие приведённой сети S j ( О ё ^ i . /п ) для п. э . п. Т 0 -*■ T j так, как это делается у Е.В.Кашинцева. Выберем на плоскости две различные точки Р ч Q. ч соединим их у + / простыми дугами t o , ■■■> 2 / . ориенти­ руя эти дуги от Р к Q (рис. I ) . Если TL = Qit CtLl . . . О ц , то дугу Г / разбиваем t ~ i вершинами (сохраняя ориентацию] на t рёбер а затем каждое ребро помечаем соответствующей буквой У ( ? ц ) = Оi t (У - функция, ставящая в соответствие каждому ориентированному пути слово в алфавите О ,, Ot , ... , ) . ¥ ( Ъ ) К ••• v ( e it ) = т£ . ___ Затем склеиваем те части дуг и Т / ( L - i , / ) , метки которых не затрагиваются при е. п. 77 -у —'* 7 / . При этом останутся не склеенными (для всех i ) часть У/ дуги У /- у и часть дуги Tt такие, что <ff ^ { ) ~ < S ( ji; ) - 82