FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

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

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

D. I. Piontkovsky

Abstract

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.

Location: http://mech.math.msu.su/~fpm/eng/k01/k012/k01211h.htm.
Last modified: October 31, 2001.