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

вующую этому сокращению. Пусть (рфйглТ) = w2w „ , w = w„w„ и /ДдВ \ Т) 3 „ Если и>не является куском, то w2w„u = ww^uw и тогда по лемме 1 w имеет ко­ нечный порядок. Значит ||w|| = 1 и \\гр(дП)\\ =3, что противоречит условию С(4). Предположим, что в слове w", п > 2, есть R - сокращение. Приклеим к от­ резку Т длинную полосу П, соответствующую этому сокращению. Если |Н | = 1, то, как следует из рассуждений леммы 3, предположение о наличии полосы в слове w" приводят к противоречиям. Если ||w|| =2, то, из тех же соображений следует, что полоса П может иметь только две области, а это означает, что w2R- сократимо, что противоречит условию леммы. Если ||w|| > 2, то такой полосы не существует в силу замечания, сделанно­ го после доказательства леммы 6 . Лемма 1 1 доказана полностью. Таким образом, в этом параграфе построены следующие алгоритмы: 1) перерабатывающие любое групповое слово в R, R - несократимое, равное ис­ ходному (лемма 9); 2) перерабатывающий любое групповое слово в цикличе­ ски R, R - несократимое, сопряженное исходному (леммы 8 , 10, 11). §4. Разрешимость проблемы вхождения Приступим непосредственно к доказательству разрешимости проблемы вхождения в циклическую подгруппу. Теорема 3. Пусть М - приведенная диаграмма, являющаяся диском (гра­ ничный цикл ( дМ) - простая замкнутая кривая), дМ= у U S, пусть tp(y), (Д8) - R, R - несократимые слова. Тогда число областей, граничащих с у и 8 одинаково. Лемма 12. Пусть М - диаграмма, как в теореме 3. Тогда в Af нет области D такой, что dDny или dDnS - несвязное множество. Доказательство. Пусть D - область в М такая, что, например, dD ny- не­ связное множество. Удалим область D из М. В результате M\D будет представ­ лена в виде дизъюнктного объединения поддиаграмм. Предположим, что их две: М\ и Мг. Пусть dDny = у\ иуъ и SD = у\ и ( dDndM^Kjft ^j(dDndM2). И предположим, что пересечение любой граничной области из Mi с у\ - связное множество. Если в Mi всего одна область По, то она деновская в М, что противоречит R- несократимости (Ду). Пусть в М\ более одной области. Пусть М0 = М,иП. Если iu0(D) = 1, го получим противоречие с предположением, сделанным вы­ 114