5. Conclusions

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 and a set of polynomials we have and , 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 .

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.

- (1)
- For all polynomials we have .
- (2)
- For all polynomials we have .

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 stands for suffix, for prefix, for quasi-commutative, for left-polycyclic reduction and 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 | none^{14} |
||

plain | none | ||

context-free | none | ||

nilpotent | |||

polycyclic | |||

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 , where , 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 is studied in [MaRe93a].