Reports on Computer Algebra (ZCA Report)
Refine
Year of publication
- 1997 (5) (remove)
Document Type
- Preprint (5)
Language
- English (5)
Has Fulltext
- yes (5)
Faculty / Organisational entity
14
A first explicit connection between finitely presented commutative monoids and ideals in polynomial rings was used 1958 by Emelichev yielding a solution tothe word problem in commutative monoids by deciding the ideal membership problem. The aim of this paper is to show in a similar fashion how congruenceson monoids and groups can be characterized by ideals in respective monoid and group rings. These characterizations enable to transfer well known resultsfrom the theory of string rewriting systems for presenting monoids and groups to the algebraic setting of subalgebras and ideals in monoid respectively grouprings. Moreover, natural one-sided congruences defined by subgroups of a group are connected to one-sided ideals in the respective group ring and hencethe subgroup problem and the ideal membership problem are directly related. For several classes of finitely presented groups we show explicitly howGröbner basis methods are related to existing solutions of the subgroup problem by rewriting methods. For the case of general monoids and submonoidsweaker results are presented. In fact it becomes clear that string rewriting methods for monoids and groups can be lifted in a natural fashion to definereduction relations in monoid and group rings.
15
16
The concept of algebraic simplification is of great importance for the field of symbolic computation in computer algebra. In this paper we review somefundamental concepts concerning reduction rings in the spirit of Buchberger. The most important properties of reduction rings are presented. Thetechniques for presenting monoids or groups by string rewriting systems are used to define several types of reduction in monoid and group rings. Gröbnerbases in this setting arise naturally as generalizations of the corresponding known notions in the commutative and some non-commutative cases. Severalresults on the connection of the word problem and the congruence problem are proven. The concepts of saturation and completion are introduced formonoid rings having a finite convergent presentation by a semi-Thue system. For certain presentations, including free groups and context-free groups, theexistence of finite Gröbner bases for finitely generated right ideals is shown and a procedure to compute them is given.
17
This paper is a continuation of a joint paper with B. Martin [MS] dealing with the problem of direct sum decompositions. The techniques of that paper areused to decide wether two modules are isomorphic or not. An positive answer to this question has many applications - for example for the classification ofmaximal Cohen-Macaulay module over local algebras as well as for the study of projective modules. Up to now computer algebra is normally dealing withequality of ideals or modules which depends on chosen embeddings. The present algorithm allows to switch to isomorphism classes which is more natural inthe sense of commutative algebra and algebraic geometry.