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

ив сегмента R j , l < / , R; - А а ' В , R j - C cl "Z> . Тогда f t ) перепишем в виде Р * К ( , ... * и » Ро S< ■■■$(А л ' В S ; . , . . . JT,- 4 /Р ^ A * R T l, t ...T ,Ca" JDT J u ...TKR ^ ^ . /2 ) Выбросим теперь из всех частей последнего равенства подслово, начинающееся с в и кончающееся словом С а " . Получим новое слово Р = R e Sf ., . S i A a ' S D S ^ . . . Так как Р -сегменты не затрагивались элементарными преобра­ зованиями в ( 2 ) , то понятно, что равенство ( 3 ) действительно выполняется в полугруппе. А так как буквы Л ' и & " имеют одинаковые типы, то из определения типа сл ед у ет, что слово Р записано через образующие подполугруппы H i и р е H it) Н х . Кроме то го , \Р l < I Р ! . Таким образом, мы пришли к противоречию с минимальностью слова Р . Рассмотрим случай 2 . В этом случае найдутся различные сегменты К у и Xfs Н е Ц ., имеющие одинаковый тип. Опять выбросим из р авен ства ( 1 ) следующие подслова: из первых трех графически равных членов - подслово, начинающееся с сегм ен та, стоящего после , и заканчивающееся сегментом X f S ; из последних двух графически равных членов - подслово, начинаю­ щееся с сегм ен та, стоящего после К(у , и заканчивающееся сегментом V fS . При этом из определения типа ..следует, что первые три члена в ( 1 ) по-прежнему будут графически равны не­ которому произведению образующих u l i , а последние два - некоторому произведению образующих V » / . О стается доказать,\ что они будут равны между собой в полугруппе и тогда мы опять получим противоречие с минимальностью слова В . Рассмотрим всевозможные поделучаи. 2 .1 . Пусть S < К у , т .е . X f s - не последний сегмент й слове % . Обозначим через Е , слово R 0 S , - - Р i~< > через Е х - ... Rh ; через Е, " Pe T t ... через Fx - P fT f t f ... RH . Надо д о к азать, что E t * ч - X4 Xt s n - * f * s Е r F< К , - f y Yh - i Yi * t F‘ • ' ( * l Так как тип сегмента AY, равен типу сегм ен та <tys , то По лемме 1 ровно один из кусков B f i » E j z P fs ) ~ ^ f s A f y*t пуст; B f t * % & A f it, - P f j , f или 75