2. Fundamental Relations Between Semi-Thue Systems and Monoid Rings

- (1)
- .
- (2)
- .

Perhaps less obvious is that
the word problem for finitely presented groups is similarly equivalent
to a restricted version of the membership problem for ideals in a
free group ring.
Let the group be presented by a semi-Thue system
such that there exists an
involution
such that for all
we have
,
,
and
the rules
and
are
included in *T*.
Such systems are called group systems.

- (1)
- .
- (2)
- .

As before, the existence of a finite group presentation over four letters (resulting from two generators) with unsolvable word problem implies that the ideal membership problem for free group rings with more than one generator is undecidable. Groups with one generator are known to have decidable word problem. The ideal membership problem for free group rings with one generator is solvable as this ring corresponds to the ring of Laurent polynomials for the (commutative) free group with one generator.

We say

- (a)
- for some , where , , and
- (b)
- .

While theorem 2.1 reduces the word problem for semi-Thue systems
to the ideal membership problem in free monoid rings, reviewing the
proof of this theorem (compare page ) we see that
in fact the existence of finite convergent semi-Thue systems
corresponds to the existence of finite Gröbner bases and vice versa.
Hence solvable word problem does not imply the existence of finite Gröbner
bases as the example of a finitely presented monoid
,
with solvable word problem but no finite
convergent presentation with respect to any admissible ordering
shows (see [KaNa85b]).
The ideal generated by the polynomial *aba* - *bab* in
has no finite Gröbner basis with respect to any admissible ordering
on .
Notice that in this example we can apply a so called Tietze transformation
to the semi-Thue system, i.e. we can change the presentation without
changing the monoid, giving us the equivalent presentation
,
which can be successfully completed, e.g. with respect to the
length-lexicographical ordering with precedence
resulting in
.
Similarly the ideal generated by
has a
finite Gröbner basis with respect to the same ordering.
Due to the result of Squire in [Sq87] there are finitely presented
monoids with solvable word problem which have no finite convergent
presentations and his examples give rise to finitely generated ideals in free
monoid rings with solvable ideal membership problem which have no
finite Gröbner bases.

So now we have seen that since finitely generated ideals in free monoid rings can have unsolvable membership problem, in general they cannot admit finite Gröbner bases. It even is possible for a finitely generated ideal to admit a finite Gröbner basis with respect to one admissible ordering and none with respect to another admissible ordering. On the other hand, in [Mo85] Mora provided a procedure which given an admissible ordering enumerates a Gröbner basis with respect to this ordering. This procedure terminates in case a finite Gröbner basis with respect to the given ordering exists. Hence the question might arise, whether it is possible to decide for a finite set of polynomials and an admissible ordering whether a finite Gröbner basis with respect to this ordering exists. This turns out to be undecidable.

The next theorem states that the subgroup problem for a group is equivalent to a special instance of the right ideal membership problem in the corresponding group ring.

- (1)
- .
- (2)
- .