## Reports on Computer Algebra (ZCA Report)

### Filtern

#### Schlagworte

- Gröbner bases (2)
- coset enumeration (2)
- subgroup problem (2)
- Abelian groups (1)
- Coxeter groups (1)
- Gröbner base (1)
- Gröbner bases in monoid and group rings (1)
- Hamiltonian groups (1)
- Monoid and group rings (1)
- Word problem (1)

- 10
- A Proposal for Syntactic Data Integration for Math Protocols (1999)
- 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.

- 11
- Effective Simplification of CR expressions (1999)
- 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.

- 2
- Algorithms in Singular (1999)

- 24
- Complete Presentations of Direct Products of Groups (1999)
- 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.

- 19
- A Note on Nielsen Reduction and Coset Enumeration (1998)
- 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.

- 22
- Some Applications Of Prefix-Rewriting In Monoids, Groups, And Rings (1998)
- 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.