Non-commutative Gr\"obner bases, coherentness of associative algebras, and divisibility in semigroups

D. I. Piontkovskii

Fundamentalʹnaâ i prikladnaâ matematika, Tome 7 (2001) no. 2, pp. 495-513.

Résumé

In the paper we consider a class of associative algebras which are denoted by algebras with $R$-processing. This class includes free algebras, finitely-defined monomial algebras, and semigroup algebras for some monoids. A sufficient condition for $A$ to be an algebra with $R$-processing is formulated in terms of a special graph, which includes a part of information about overlaps between monomials forming the reduced Gröbner basis for a syzygy ideal of $A$ (for monoids, this graph includes the information about overlaps between right and left parts of suitable string-rewriting system). Every finitely generated right ideal in an algebra with $R$-processing has a finite Gröbner basis, and the right syzygy module of the ideal is finitely generated, i. e. every such algebra is coherent. In such algebras, there exist algorithms for computing a Gröbner basis for a right ideal, for the membership test for a right ideal, for zero-divisor test, and for solving systems of linear equations. In particular, in a monoid with $R$-processing there exist algorithms for word equivalence test and for left-divisor test as well.