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
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 -processing.
This class includes free algebras, finitely-defined monomial algebras,
and semigroup algebras for some monoids.
A sufficient condition for to be an algebra
with -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 (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
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 -processing there exist
algorithms for word equivalence test and for left-divisor test as
All articles are
published in Russian.
Last modified: October 31, 2001.