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.