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

получающиеся из MD описанным в определении 7 способом. Через Mn щ будеь< обозначать диаграмму (А/д)о/, а через МПА диаграмму (ЛДД . Поскольку этот процесс может продолжаться (далее покажем, что он ко- нечен), то при любом натуральном т будем обозначать через М ^ диа- . _____ т,п грамму (,..((Л/£>! )д 2 )...)д я и пусть М ^...От = MD^ ( U Di)- ;=i,y=i Замечание. Из доказательства леммы 4 можно сделать вывод, что в диа­ грамме М нет длинных деновских областей, т.е. областей, описанных в п. 2 . 2 , и п.2.3, (для них теорема 1 имеет место). Поэтому далее будем иметь дело только с короткими деновскими областями, т.е. когда |и| =\<p(cDп, 8М)\ < |w|. Если в диаграмме М есть короткая полоса П, то можно определить р - преобразование аналогично d - преобразованию. Пусть в диаграмме М есть деновская область D типаД . Будем считать, что диаграммы М, MD имеют равное число кусков в граничных метках, в про­ тивном случае утверждение теоремы следует из индуктивного предположения. Определение 9. Короткая деновская область D [Полоса П] в диаграмме М называется точной, если начало или конец пути SD п дМ [дП о дЩ является первичной вершиной. Рассмотрим диаграмму MD. Её граница уже разбита на рёбра и вершины ‘ этого разбиения будем считать первичными в MD. Деновская область D, е М0 . .. . ; • . '.у ■ ( ;ч.•.. ' • ‘ ■ называется точной, если начало или конец пути q = 3D, п дМ0 - первичная вершина из дМ0. Из определения точной области следует, что если в диаграмме М с мет­ кой <р(дМ) s й>" есть точная деновская область D типа Д , то задача со словом vv” сводится к задаче со словом w f , где Wj - слово, получающееся из w заменой подслова U\ = <Po{dD п дМ) словом и = <pD(8D \ дМ)Л и ||ит|| < ||и>||. Поэтому далее будем считать, что диаграммы Л/, Л Д , АД 0 не содержат точных деновских ■ 1 , ..»( : ...KWfH 104