Аннотация:
Для полугрупп, задаваемых одним несократимым слева определяющим соотношением, предлагается алгоритм построения кратчайшего вывода делимости слева произвольного слова на данную букву алфавита полугруппы. При этом гарантируется, что алгоритм завершает работу каждый раз, когда такая делимость фактически имеет место в рассматриваемой полугруппе. Принципиальное значение для приложений имеет открытый пока вопрос о распознавании терминируемости предлагаемого алгоритма хотя бы для полугрупп с двумя порождающими и одним определяющим соотношением.
|
