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

Чтобы определить граничные ребра односвязной диаграммы М, разобьем оМ на отрезки, которые высекаются на ней граничными областями из М. Каж­ дый из этих отрезков имеет метку, которую можно представить в виде произве­ дения минимального числа кусков (см. замечание ниже). В соответствии с та­ ким представлением этих меток разобьем уже имеющиеся отрезки на более мелкие, которые и назовем граничными ребрами диаграммы М . Иногда приходится уточнять, в какой поддиаграмме читается метка пути. Для краткости будем указывать эту поддиаграмму в нижнем индексе функции метки q>U[(дМ, г\дМг). Множество слов R удовлетворяет условию Р, если все куски имеют еди­ ничную длину. Вопрос о разрешимости рассматриваемой проблемы в группах с условием С( р)&T(q)& Р поставлен в [2]. Обозначим через ju длину слова и , а через и ! - минимальное число кус­ ков, на которые можно разбить слово и . Графическое равенство слов и , v обо­ значим через ws v, а сопряженность: u ~ v . Если М - диаграмма, то через М будем обозначать ее площадь (число областей в М ). Замечание [6]. Любое определяющее соотношение можно разбить на кус­ ки, так как любая буква х е Х является куском, либо может быть удалена при помощи преобразования Лице без нарушения условия С(б). Определение 1.1. В слове месть R -сокращение, если: 1) либо существует слово r e R такое, что и^и,щи,, г = m 2V2, гу е {1,2}, слова м,г2 и г2м3 несократимы в свободной группе F = F (X ), ( r2j= 0 тогда и только тогда, когда г, =0), и тогда Л-сокращение состоит в замене слова и словом М|Г3н3; 2) либо существует слово r e R такое, что msh , m 2 m 3, г&и2, слово м,м3, возможно, сократимо в F, и тогда Л-сокращение состоит в замене слова и словом uiui с последующей заменой последнего равным несократимым в F словом. 27