5. Conclusions

We have shown how reduction can be introduced to monoid and group rings and how Gröbner bases can be characterized. Our approach involves techniques as saturation, since the general absence of a well-founded compatible ordering causes severe problems. The technique of saturating a set of rules or relations is frequently used by completion based approaches in computer algebra and theorem proving. E.g. symmetrization of a group as described by Le Chenadec [LeCh86], symmetrized sets for free Abelian group rings as defined by Sims [Si94], right orbits for free group rings as defined by Rosenmann [Ro93], or multiplication by non-Pommaret-multiplicatives as described by Zharkov and Blinkov [ZhBl93] all have the same idea in common and can be subsumed under the concept of saturation. In fact the methods of Sims and Rosenmann correspond to special cases of our approach. The method of Zharkov and Blinkov and their definition of involutive bases which Apel has compared to Gröbner bases in [Ap95], corresponds directly to the computation of interreduced suffix Gröbner bases in the commutative polynomial ring viewed as a free commutative monoid ring.

The weakening of strong right reduction presented here is prefix reduction. This reduction has a finitary local confluence test and terminating procedures to compute finite prefix Gröbner bases for finitely generated right ideals in the classes of finite, free, plain respectively context-free groups, were given. So all these rings are examples of effective one-sided reduction rings. An implementation is on the way. Furthermore, in [Re95] we have shown that prefix reduction satisfies axiom (A4) and hence successfully introduced the concept of interreduction to prefix Gröbner bases. Interreduction and critical-pair criteria are closely related to notions of redundancy as considered in general theorem proving [BaGa94a].

Of course prefix reduction is not the appropriate weakening for every structure. There are cases were finitely generated strong Gröbner bases exist but no finite prefix ones, e.g. in general in commutative structures. Nevertheless they can be used to compute a strong Gröbner basis, since such a basis is always contained in the weaker one [ZhBl93]. In [Re95] other ways of weakening strong right reduction for special structures are developed and studied, e.g., for commutative monoids and nilpotent groups. Terminating algorithms for computing Gröbner bases of both, right and two-sided ideals, in commutative monoid rings and nilpotent group rings are provided. The key idea used is as follows:

(1)

Define a weakening of strong reduction, say w-reduction, appropriate to the respective structure in the following sense:
If for some polynomials $p, g \in {\bf K}[{\cal M}]$ and a set of polynomials $F \subseteq {\bf K}[{\cal M}]$ we have $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm w}}_{g}\,$ } 0$ and $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm w}}_{F}\,$ } 0$, then there exists a representation of p in terms of F such that one term in this representation equals the head term of p and all other terms are smaller with respect to the ordering on ${\cal M}$.
Variations of this lemma are e.g. the lemmata 3.22 and 3.30.

(2)

Define saturation with respect to w-reduction.

(3)

Define s-polynomials with respect to w-reduction.

Then in case the translation lemma holds for w-reduction, a characterization of w-Gröbner bases of right ideals as follows is possible:

For a w-saturated set $F \subseteq {\bf K}[{\cal M}]$ the following statements are equivalent:

(1)

For all polynomials $g \in {\sf ideal}_{r}^{}(F)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm w}}_{F}\,$ } 0$.

(2)

For all polynomials $f_{k}, f_{l} \in F$ we have ${\sf spol}_{w}(f_{k}, f_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm w}}_{F}\,$ } 0$.

In order to get an effective procedure from this characterization some finiteness and computability conditions have to be satisfied.

Similar to theorem 3.34 w-Gröbner bases of two-sided ideals can be characterized and enumerating procedures can be given.

This approach has been successfully applied to special groups. The class of finitely presented groups contains subclasses which - using appropriate presentations - allow to solve the subgroup problem using string-rewriting techniques. In [MaRe97b] we have pointed out how these results are related to the existence (and in fact even the construction) of Gröbner bases in the respective group rings. This shall now be summarized in the following table, which lists the reductions which - again using appropriate presentations for the groups - ensure the construction of the respective finite Gröbner basis of ideals. Note that $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm su}}_{}\,$ }$ stands for suffix, $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$ for prefix, $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{}\,$ }$ for quasi-commutative, $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$ for left-polycyclic reduction and $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{}\,$ }$ for right-polycyclic reduction (for more information on the reductions and the computation of Gröbner bases related to them see [MaRe93b,Re95,MaRe96a,MaRe97a,Re96]).

Group	left ideals	right ideals	two-sided ideals
free	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm su}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$	none14
plain	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm su}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$	none
context-free	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm su}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$	none
nilpotent	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{}\,$ }$
			$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$
polycyclic	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{}\,$ }$	$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$
			$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{}\,$ }$

As mentioned above, the different reductions require special forms of presentations for the respective groups. Free groups need free presentations with length-lexicographical completion ordering for prefix and suffix reduction. Plain groups require canonical 2-monadic presentations with inverses of length 1 and again length-lexicographical completion ordering for prefix as well as suffix reduction. Context-free groups demand virtually free presentations (see [CrOt94]) for prefix and a modified version of these presentations for suffix reduction. All these special forms of the presentations are similarly required when solving the subgroup problem using prefix-rewriting techniques. For nilpotent groups we need convergent so called PCNI-presentations for quasi-commutative and left-polycyclic reduction. In the case of polycyclic groups we need PCP-presentations for left-polycyclic and reversed PCP-presentations for right-polycyclic reduction.

Alternatives to restricting reduction by incorporating more and more structural knowledge in order to get finite bases were developed in the field of term rewriting. One problem related to the Knuth-Bendix procedure is that it diverges for many cases and it is in general undecidable if it will diverge on a given input. Resulting from this many people have studied what patterns of rules might cause such a divergence. Several methods to solve divergence problems have been offered in order to detect infinite sets of rules which share certain structural regularities e.g. by using constraints, recurrence schemes or auxiliary operators and/or sorts. In the context of string rewriting convergent regular presentations for monoids and groups are considered and inductive inference methods have been proposed to detect the patterns. Another possibility is to follow the approach given by Deiß in [De92] of defining conditional semi-Thue systems and to develop a concept of ``conditional polynomial rewriting''. Nevertheless, Sattler-Klein in [Sa96] has shown that such approaches are limited. This is due to her result that any recursively enumerable subset of ${\bf N}^n$, where $n \in{\bf N}^+$, can be encoded into a canonical system generated by completion.

As mentioned in the introduction, when one is solely interested in solving the membership problem a Gröbner basis with its confluence property is not necessary. Alternatives known from term rewriting are unfailing completion or confluence on special equivalence classes only. Our definitions of reduction in monoid rings so far always guarantee overall confluence since the translation lemma holds. In order to approach other group rings or to develop other techniques, ``weaker'' forms of reduction should be considered, especially for those cases where the subgroup problem for the group is solvable by partial confluence but not by confluence.

Furthermore, in [Re95] we have shown how the theory of Gröbner bases in monoid and group rings over fields can be lifted to monoid and group rings over reduction rings fulfilling the axioms given in the introduction and some computability conditions, e.g., allowing to compute finite Gröbner bases for ideals in the coefficient domain. Hence the results of this paper also hold for monoid and group rings over reduction rings, e.g., the case of the integers ${\bf Z}$ is studied in [MaRe93a].