АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

определяющего слова полугруппы в качестве истинного под­ слова, то равенство Ч’(С^) = является определяющим с о ­ отношением в полугруппе G . Докажем сначала, что и УК&О не содержат опре­ деляющих слов полугруппы о&г в качестве истинных подслов. В самом д еле, если, например, vf~ fA )* X Q Y * где А - это At или и Q - определяющее слово минимальной длины,со­ держащееся в ^ ( А ) , т . е . не содержащее других определяющих сл ов, тогда Y ( f i ) является определяющим словом полугруппы ■ G и из тождества А н 'Щ ()чР(С|)'Р(У) ш получаем противоре­ чие условию р< I определения полугруппы С* . Равенство ^ ( Д ч ) « Ч ^ О к ) ('К i <■•=.) в полугруппе означает, что существует конечная последовательность под­ становок от 4 м (Al.) до ( 2 ) T 4 A i ) - F „ = . . . = F p = 4 м ( В О - Предполагая, без ограничения общности, что последователь­ ность (2 ) является самой короткой из всех возможных, имеем: , и Т е * F j при t * j . В связи с тем, что 'P ( A i ) не содержит определяющих слов полугруппы * отличных от се б я , равенство Y м (Ai) = Ти является определяющим соотношением в и Лч= У(Рч) являет­ ся определяющим соотношением в & . Следовательно, R, = - Y >' 4 vf(F < )) не содержит определяющих слов из ^ в качест­ ве истинных подслов и при р > I равенство = является определяющим соотношением в и * согласно пункту 2 ) опи­ сания алгоритма, ' f ^ (Ач) * Гс также является определяющим соотношением, но это противоречит ш бору последовательности подстановок (,2) от слова Д о слова 'f-* ( Ъ\) , кото­ рая, по определению, является самой короткой из всех возмож­ ных. Таким образом, I и является опреде­ ляющим соотношением в . Т .к . Cj в полугруппе и Ч " изоморфизм, то 'f(CJj)*Y (P j)Q « I .....5 ^ ) в полугруппе & . Теорема 2 доказана. Результаты данной работы без доказательства были опубли­ кованы в Ш и C2J, - 9 -