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

УДК 419.4 D. Э.ТРУБИЦЫН НПО "Ока", г.Тула «УНШИ ДЛИНЫ И ПРОБЛЕМА равенства в голугруппах В статье М.Д.Гриндяингера и Е.И.Гриндлингер [ i ] рассматри­ вался класс конечно-определённых полугрупп, удовлетворяющих некоторым условиям. Было доказано, что любое слово полугруппы П из этого класса равно в П конечному числу слов, и, сле­ довательно, проблема равенства в этих полугруппах разрешима. В данной статье доказывается аналогичная теорема для более широкого класса полугрупп. Расширение достигается за счёт при­ менения функций длины (см. определение 2 ). Кроме того, получены некоторые результаты о полугруппах с малым налеганием определяю­ щих- слов. Д алее графическое равенство слов будем обозначать знаком = . § I . FE С -представления Рассмотрш полугруппу П = < ол , . . К ; A i =Вс , L e l > ц ) с конечным множеством образующих и рекурсивным множеством оп­ ределяющих соотношений, причём все А, , В{ - непустые слова. ОЙРВДлЛьНИЁ I . Представление ( 1) называется FE С -представлением для полугруппы /7 (а сама полугруппа - F E C -представленной), если с помощью определяющих соотно­ шений Ai = В, из ( I ) любое слово в алфавите £ 0 1у можно перевести лишь в конечное число графически различных слов. Полугруппа, которую можно задать F E С -представлением, называется F E C -полугруппой. Каждому слову Р = а , , ... а1т в алфавите = {<?,, ■■, а п \ соответствует число д ( Р ) ~т - его длина. Можно считать, что д (Ai) } д ( В £) для всех индексов L . ОПРЕДЕЛЕНИЕ 2. Будем говорить, что на полугруппе (I) задана функция длины S , если S - это отображение, ставя­ щее в соответствие каждому слову в алфавите IL целое неотри­ цательное число таким образом, что для любых слов Р , Q в алфавите I t и любого^определяющего соотношения A i - Вt полугруппы П выполняется условие 5 ( РА, Q) - S (Р8; Q) - s (A J - S ( e l ) 74-