2001, VOLUME 7, NUMBER 2, PAGES 495-513

Non-commutative Gröbner bases, coherentness of associative algebras, and divisibility in semigroups

D. I. Piontkovsky


View as HTML     View as gif image    View as LaTeX source

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.

All articles are published in Russian.

Main page Contents of the journal News Search

Last modified: October 31, 2001.