KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Mon, 03 Apr 2000 00:00:00 +0200Mon, 03 Apr 2000 00:00:00 +0200MRC - A System for Computing Gröbner Bases in Monoid and Group Rings
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/472
Gröbner bases and Buchberger's algorithm have been generalized to monoid and group rings. In this paper we summarize procedures from this field and present a description of their implementation in the system Mrc V 1.0.Birgit Reinert; Dirk Zeckzerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/472Mon, 03 Apr 2000 00:00:00 +0200SINGULAR version 1.2 User Manual
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/473
Gert-Martin Greuel; Gerhard Pfister; Hans Schönemannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/473Mon, 03 Apr 2000 00:00:00 +0200A Proposal for Syntactic Data Integration for Math Protocols
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/462
The problem of providing connectivity for a collection of applications is largely one of data integration: the communicating parties must agree on thesemantics and syntax of the data being exchanged. In earlier papers [#!mp:jsc1!#,#!sg:BSG1!#], it was proposed that dictionaries of definitions foroperators, functions, and symbolic constants can effectively address the problem of semantic data integration. In this paper we extend that earlier work todiscuss the important issues in data integration at the syntactic level and propose a set of solutions that are both general, supporting a wide range of dataobjects with typing information, and efficient, supporting fast transmission and parsing.Olaf Bachmann; Hans Schönemannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/462Mon, 03 Apr 2000 00:00:00 +0200Effective Simplification of CR expressions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/463
Chains of Recurrences (CRs) are a tool for expediting the evaluation of elementary expressions over regular grids. CR based evaluations of elementaryexpressions consist of 3 major stages: CR construction, simplification, and evaluation. This paper addresses CR simplifications. The goal of CRsimplifications is to manipulate a CR such that the resulting expression is more efficiently to evaluate. We develop CR simplification strategies which takethe computational context of CR evaluations into account. Realizing that it is infeasible to always optimally simplify a CR expression, we give heuristicstrategies which, in most cases, result in a optimal, or close-to-optimal expressions. The motivations behind our proposed strategies are discussed and theresults are illustrated by various examples.Olaf Bachmannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/463Mon, 03 Apr 2000 00:00:00 +0200MP Prototype Specification
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/464
Olaf Bachmann; S. Gray; Hans Schönemannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/464Mon, 03 Apr 2000 00:00:00 +0200Relating Rewriting Techniques on Monoids and Rings: Congruences on Monoids and Ideals in Monoid Rings
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/465
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.Klaus Madlener; Birgit Reinertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/465Mon, 03 Apr 2000 00:00:00 +0200Splitting algorithm for vector bundles
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/466
A new criteria for indecomposability of vector bundles on projective varieties is presented. It is deduced from a new finite algorithm computing direct sumdecompositions of graded modules over graded algebras. This algorithm applies as well to modules over local complete algebras over a field.Bernd Martin; Thomas Siebertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/466Mon, 03 Apr 2000 00:00:00 +0200String Rewriting and Gröbner Bases - A General Approach to Monoid and Group Rings
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/467
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.Klaus Madlener; Birgit Reinertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/467Mon, 03 Apr 2000 00:00:00 +0200An algorithm for constructing isomorphisms of modules
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/468
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.Thomas Siebertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/468Mon, 03 Apr 2000 00:00:00 +0200Monomial Representations for Gröbner Bases Computations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/469
Monomial representations and operations for Gröbner bases computations are investigated from an implementation point of view. The technique ofvectorized monomial operations is introduced and it is shown how it expedites computations of Gröbner bases. Furthermore, a rank-based monomialrepresentation and comparison technique is examined and it is concluded that this technique does not yield an additional speedup over vectorizedcomparisons. Extensive benchmark tests with the Computer Algebra System SINGULAR are used to evaluate these concepts.Olaf Bachmann; Hans Schönemannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/469Mon, 03 Apr 2000 00:00:00 +0200A Note on Nielsen Reduction and Coset Enumeration
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/470
Groups can be studied using methods from different fields such as combinatorial group theory or string rewriting. Recently techniques from Gröbner basis theory for free monoid rings (non-commutative polynomial rings) respectively free group rings have been added to the set of methods due to the fact that monoid and group presentations (in terms of string rewriting systems) can be linked to special polynomials called binomials. In the same mood, the aim of this paper is to discuss the relation between Nielsen reduced sets of generators and the Todd-Coxeter coset enumeration procedure on the one side and the Gröbner basis theory for free group rings on the other. While it is well-known that there is a strong relationship between Buchberger's algorithm and the Knuth-Bendix completion procedure, and there are interpretations of the Todd-Coxeter coset enumeration procedure using the Knuth-Bendix procedure for special cases, our aim is to show how a verbatim interpretation of the Todd-Coxeter procedure can be obtained by linking recent Gröbner techniques like prefix Gröbner bases and the FGLM algorithm as a tool to study the duality of ideals. As a side product our procedure computes Nielsen reduced generating sets for subgroups in finitely generated free groups.Birgit Reinert; Klaus Madlenerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/470Mon, 03 Apr 2000 00:00:00 +0200Algorithms in Singular
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/471
Hans Schönemannpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/471Mon, 03 Apr 2000 00:00:00 +0200On an implementation of standard bases and syzygies in SINGULAR
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/461
Hubert Grassmann; Gert-Martin Greuel; Bernd Martin; W. Neumann; Gerhard Pfister; W. Pohl; Hans Schönemann; Thomas Siebertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/461Mon, 03 Apr 2000 00:00:00 +0200MPP: A Framework for Distributed Polynomial Computations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/474
Olaf Bachmann; Hans Schönemann; S. Graypreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/474Mon, 03 Apr 2000 00:00:00 +0200Advances and improvements in the theory of standard bases and syzygies
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/475
Gert-Martin Greuel; Gerhard Pfisterpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/475Mon, 03 Apr 2000 00:00:00 +0200Description of SINGULAR: A Computer Algebra System for Singularity Theory, Algebraic Geometry and Commutative Algebra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/476
Gert-Martin Greuelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/476Mon, 03 Apr 2000 00:00:00 +0200On strategies and implementations for computations of free resolutions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/477
Thomas Siebertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/477Mon, 03 Apr 2000 00:00:00 +0200Introducing Reduction to Polycyclic Group Rings - A Comparison of Methods
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/478
t is well-known that for the integral group ring of a polycyclic group several decision problems are decidable. In this paper a technique to solve themembership problem for right ideals originating from Baumslag, Cannonito and Miller and studied by Sims is outlined. We want to analyze, how thesedecision methods are related to Gröbner bases. Therefore, we define effective reduction for group rings over Abelian groups, nilpotent groups and moregeneral polycyclic groups. Using these reductions we present generalizations of Buchberger's Gröbner basis method by giving an appropriate definition of"Gröbner bases" in the respective setting and by characterizing them using concepts of saturation and s-polynomials.Birgit Reinertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/478Mon, 03 Apr 2000 00:00:00 +0200Some Applications Of Prefix-Rewriting In Monoids, Groups, And Rings
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/792
Rewriting techniques have been applied successfully to various areas of symbolic computation. Here we consider the notion of prefix-rewriting and give a survey on its applications to the subgroup problem in combinatorial group theory. We will see that for certain classes of finitely presented groups finitely generated subgroups can be described through convergent prefix-rewriting systems, which can be obtained from a presentation of the group considered and a set of generators for the subgroup through a specialized Knuth-Bendix style completion procedure. In many instances a finite presentation for the subgroup considered can be constructed from such a convergent prefix-rewriting system, thus solving the subgroup presentation problem. Finally we will see that the classical procedures for computing Nielsen reduced sets of generators for a finitely generated subgroup of a free group and the Todd-Coxeter coset enumeration can be interpreted as particular instances of prefix-completion. Further, both procedures are closely related to the computation of prefix Gr"obner bases for right ideals in free group rings.Klaus Madlener; Otto Friedrichpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/792Thu, 11 Nov 1999 00:00:00 +0100Observations on coset enumeration
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/793
Todd and Coxeter's method for enumerating cosets of finitely generated subgroups in finitely presented groups (abbreviated by Tc here) is one famous method from combinatorial group theory for studying the subgroup problem. Since prefix string rewriting is also an appropriate method to study this problem, prefix string rewriting methods have been compared to Tc. We recall and compare two of them briefly, one by Kuhn and Madlener [4] and one by Sims [15]. A new approach using prefix string rewriting in free groups is derived from the algebraic method presented by Reinert, Mora and Madlener in [14] which directly emulates Tc. It is extended to free monoids and an algebraic characterization for the "cosets" enumerated in this setting is provided.Birgit Reinertpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/793Thu, 11 Nov 1999 00:00:00 +0100Complete Presentations of Direct Products of Groups
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/794
Complete presentations provide a natural solution to the word problem in monoids and groups. Here we give a simple way to construct complete presentations for the direct product of groups, when such presentations are available for the factors. Actually, the construction we are referring to is just the classical construction for direct products of groups, which has been known for a long time, but whose completeness-preserving properties had not been detected. Using this result and some known facts about Coxeter groups, we sketch an algorithm to obtain the complete presentation of any finite Coxeter group. A similar application to Abelian and Hamiltonian groups is mentioned.Miguel Borges-Trenard; Hebert Perez-Rosespreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/794Thu, 11 Nov 1999 00:00:00 +0100