ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2001, ТОМ 7, ВЫПУСК 2, СТР. 495-513

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

Д. И. Пионтковский

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

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

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

Полнотекстовая версия статьи в формате PostScript (79 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k01/k012/k01211h.htm.
Изменения вносились 31 октября 2001 г.