## On Gröbner Bases in Monoid and Group Rings

- Following Buchberger's approach to computing a Gröbner basis of a poly-nomial ideal in polynomial rings, a completion procedure for finitely generatedright ideals in Z[H] is given, where H is an ordered monoid presented by a finite,convergent semi - Thue system (Sigma; T ). Taking a finite set F ' Z[H] we get a(possibly infinite) basis of the right ideal generated by F , such that using thisbasis we have unique normal forms for all p 2 Z[H] (especially the normal formis 0 in case p is an element of the right ideal generated by F ). As the orderingand multiplication on H need not be compatible, reduction has to be definedcarefully in order to make it Noetherian. Further we no longer have p Delta x ! p 0for p 2 Z[H]; x 2 H. Similar to Buchberger's s - polynomials, confluence criteriaare developed and a completion procedure is given. In case T = ; or (Sigma; T ) is aconvergent, 2 - monadic presentation of a group providing inverses of length 1 forthe generators or (Sigma; T ) is a convergent presentation of a commutative monoid ,termination can be shown. So in this cases finitely generated right ideals admitfinite Gröbner bases. The connection to the subgroup problem is discussed.

Author: | Klaus Madlener, Birgit Reinert |
---|---|

URN (permanent link): | urn:nbn:de:hbz:386-kluedo-3196 |

Serie (Series number): | SEKI Report (93,8) |

Document Type: | Preprint |

Language of publication: | English |

Year of Completion: | 1999 |

Year of Publication: | 1999 |

Publishing Institute: | Technische Universität Kaiserslautern |

Date of the Publication (Server): | 2000/04/03 |

Faculties / Organisational entities: | Fachbereich Informatik |

DDC-Cassification: | 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik |

Licence (German): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |