Некоммутативные базисы Грёбнера, когерентность ассоциативных алгебр и делимость в полугруппах

В статье изучается класс ассоциативных алгебр, которые мы называем алгебрами с $R$-переработкой. Этот класс включает свободные и конечно определённые мономиальные алгебры, а также полугрупповые алгебры для некоторых моноидов. Достаточный признак алгебры $A$ с $R$-переработкой можно сформулировать в терминах специального графа, кодирующего информацию о пересечениях между одночленами, составляющими редуцированный базис Грёбнера идеала соотношений $A$ (для моноидов — информацию о пересечениях между правыми и левыми частями соответствующей переписывающей системы). В алгебре с $R$-переработкой всякий конечно порождённый правый идеал обладает конечным базисом Грёбнера и его правый модуль соотношений конечно порождён, то есть такая алгебра когерентна. В таких алгебрах существуют алгоритмы построения базиса Грёбнера правого идеала, распознавания вхождения в правый идеал, распознавания левых делителей нуля и решения систем линейных уравнений. В частности, в моноиде с $R$-переработкой алгоритмически разрешима не только проблема равенства слов, но и проблема левой делимости.