Next: 4. Relating the Word
Up: Relating Rewriting Techniques on
Previous: 2. Presentations: Congruences in
3. Relating the Word and the
Ideal Membership Problems in Monoids and Free Monoid Rings
Let us start this section with some algebraic notions concerning monoid
rings.
For a monoid
with multiplication
and a total wellfounded
ordering
on ,
the elements of the monoid ring
over a field
can
be presented as ``polynomials''
where only finitely many
are nonzero.
The elements
are called monomials consisting of a
coefficient
and a term t.
Addition and multiplication
for two polynomials
and
is defined as
and
with
.
Given a nonzero polynomial p in
,
the head term
is the
largest term in p with respect to ,
which has nonzero coefficient
denoted by
,
and the head monomial is
.
is the set of all
with nonzero coefficient in p.
For a subset F of
we call the set
^{5} the right ideal,
the left ideal and
the twosided ideal
generated by F.
By
we will denote the (right, left respectively twosided) congruence
induced by a (right, left respectively twosided) ideal
on
.
The following theorem states that the word problem for monoids
is equivalent to a restricted version of the ideal membership
problem in free monoid rings.
This immediately implies the undecidability of the latter problem which is also
stated in [Mo87,KaWe90], but the proof we give here
provides a stronger result outlined below.
For a string rewriting system
presenting a
monoid, the related free monoid ring is
,
where
is the free monoid generated by
with word concatenation as binary operation and
as identity element.
Theorem 1
Let
be a finite string rewriting system presenting a monoid
and
a set of polynomials in
associated with
T.
Then for
the following statements are equivalent:
 (1)

,
i.e. the relation u=v holds in .
 (2)

.
Proof :
1.11.1
Next: 4. Relating the Word
Up: Relating Rewriting Techniques on
Previous: 2. Presentations: Congruences in
 ZCA Home 
Reports 