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

и конечным числом определяющих соотно’ зний = •• • ! / « ■ ) • ( 2 ) Полугруппу П , заданную образующими ( I ) и определя­ ющими соотношениями ( 2 ) , будем обозначать: П - < a ^ a . z , . . а. ^ ; А £ = 3 ; > - ' (3) Пусть - произвольное слово полугруппы П , задан­ ное в алфавите ( I ) и [£ =й £- &, OL- , где =: означает - графическое равенство слов в полугруппе. Тогда число вхож­ дений букв алфавита ( I ) в слово W назовем длиной этого слова и обозначим . Так в нашем случае = , Если I . . a ^ rSPr , ТО под слоговой ДЛИНОЙ зТОГО слова L ( X ') будем понимать число вхождений букв (X ъ $ в слово W * , которое получается из слова W , если положить в нем ^ = / 1 = - . Равенство слов в полугруп­ п е, в отличие от графического равенства, будем обозначать зншсом = . Определяющим словом назовем олово, представля­ ющее собой левую и правую часть соотношения (2). Такое про­ извольное слово обозначим с1- . Если некоторое слово t vW\XB, то X называется подсловом слова 1л/ . В случае, когда , хотя бы одно из слов А или 8 .не пусто, X называется истинным подсловом слова W . Пусть А - В некоторое равенство, где каждое из слов А и В есть некоторое слово в счетном алфавите } . Будем считать, что тождество А ~ В выполняется в полу­ группе П , если при любом гомоморфном отображении У* свободной полугруппы, порожденной 7 , в П вначения слов ' f ( A ) и У ’( В ) равны в /7 , т . е . А — В становится равен­ ством в полугруппе Г] при подстановке в слова ,4 и В вместо элементов из 2 . любнх элементов из П . Например, во всякой коммутативной полугруппе имеет место тождество Свободной назовем такую полугруппу ( 3 ) , у которой мно­ жество определяющих соотношений пусто, или любую изоморфную ей. Число образующих свободной полугрупп:., у .ко­ торой множество соотношений пусто, будеи к ? за - вать ее рангом. Тождество, если оно вы. эл- - 123 -