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

Определение 1.2. Граничная область D в диаграмме М называется денов- ской, если 1) d D n d M - последовательная часть границы d М (см. [1, стр.332]); 2 ) /(D) g {0,1,2}, d D n d M - связное множество. Определение 1.3. В слове месть Л-сокращение, если существуют слова г,.... гк из R такие, что и == u0uv..uM ; г, = г'г*г*г*, и , s (г/)г'(/ = 1 к),г* * (гД,)"'(* = 1,...,* - 1), И* = l(i = =2 при k> 2 (i= 2 ,...,k -\), = Ь 1 =Ы “ ••Jr*1= И = слово uarl2rk^...rkrkukt | несократимо в F . R -сокращение состоит в замене слова и равным ему в G словом uQri1rl3r^...uk у,. Определение 1.4. Поддиаграмма П = (J?_| D, в диаграмме М называется полосой, если 1) множество dDx п дМ связно и является последовательной частью границы дМ; 2) множество дП п дМ связно и является последовательной частью гра­ ницы дМ\ 3) /(D1) = /(A )= 3 ; 4 ) п р и £ >2 »(Д)=4, 1=2,...,к - 1; 5) dD\ n 3 D ltl - ребро, / = 1.... к - 1; 6) dDi n dD j = 0 при 7 - j\ > 1. Если в любой циклической перестановке и слова и нет Л^/ f j -сокращений, то слово и циклически Л, Л-несократимо. Лемма 1.1. [3]. Существует алгоритм, строящий по любому циклически несократимому в свободной группе слову «циклически Л,Л-несократимое слово и0, сопряженное с и в группе G . 28