### Mathematics Preprints 2006

# Computational Discrete Algebra

#### 06.05 : HEYWORTH, A. & WENSLEY, C.D.

### IdRel 2.02 : a deposited share package for GAP

#### Summary:

The**IdRel**share library package is designed for computing the identities among relations of a group presentation using rewriting, logged rewriting, monoid polynomials, module polynomials and Y-sequences.

Version 1.001 of **IdRel** formed part of Anne Heyworth's PhD thesis in
December 1999.

Version 2.02 was prepared for the **GAP 4.4** release in March 2006.

The package may also be obtained from the Bangor ftp pages for Computational Higher-dimensional Discrete Algebra.

#### 06.06 : HEYWORTH, A. & WENSLEY, C.D.

### Kan 0.93 : a deposited share package for GAP

#### Summary:

The**kan**package started out as part of Anne Heyworth's thesis, and was designed to compute induced actions of categories.

This version of **kan** only provides functions for the computation
of normal forms of representatives of double cosets
of finitely presented groups,
and is made available in support of the paper
05.07.

This version of kan has been prepared for GAP~4.4.6.
Some of the functions in the **automata** share package are used
to compute word acceptors and regular expressions
for the languages they accept.
The **kbmag** share package is also used to compute
a word acceptor of a group G when G has no finite rewriting system.

The package may also be obtained from the Bangor ftp pages for Computational Higher-dimensional Discrete Algebra.

#### 06.07 : MOORE, E.J. & WENSLEY, C.D.

### Gpd 1.01 : a deposited share package for GAP

#### Summary:

This package formed part of Emma Moore's Ph.D. thesis in December 2000.It was originally called

**GraphGpd**, but not made generally available.

Version 1.003 for

**Gap 4.4**was made in January 2004.

After extensive revision, concentrating more on the functions for groupoids
rather than those for graphs of groups,

version 1.01 of **Gpd** was made available on 17th May 2006.

The following structures are implemented:

- groupoids (categories with every element invertible) and their morphisms;
- graphs of groups, and reduction of words to normal form;
- graph of groups rewriting systems for free products with amalgamation and for HNN extensions;
- graphs of groupoids, and reduction of words to normal form.

Computationally, there are three types of connected groupoid:

- those with identical object groups,
- those with object groups conjugate in some supergroup,
- those with object groups which are just isomorphic.

**GraphGpd**attempted to implement the second case.

**Gpd 1.01**restricts itself to the first case.

**Gpd 1.02**will extend 1.01 to the second case.

The package may also be obtained from the Bangor ftp pages for Computational Higher-dimensional Discrete Algebra.

#### 06.14 : EVANS, G.A.

### On Noncommutative Involutive Divisions

#### Abstract:

Buchberger's algorithm for computing a Groebner basis solves the ideal membership problem over commutative polynomial rings.In the early 1990's, an alternative to this algorithm was found, namely the involutive basis algorithm, which provides a Groebner basis with extra combinatorial properties.

Buchberger's work was generalised to noncommutative polynomial rings by Bergman and Mora during the 1970's and 1980's.

This article provides the corresponding generalisation for involutive bases, providing a noncommutative involutive basis algorithm, and analysing several noncommutative involutive divisions for use with the algorithm.

#### Download:

06_14.pdf#### Published in:

#### 06.16 : EVANS, G.A. & WENSLEY, C.D.

### Complete involutive rewriting systems

#### Abstract:

Given a monoid string rewriting system*M*, one way of obtaining a complete rewriting system for

*M*is to use the classical Knuth-Bendix critical pairs completion algorithm. It is well known that this algorithm is equivalent to computing a noncommutative Groebner basis for

*M*. This article explains how to use noncommutative involutive basis methods to obtain a complete involutive rewriting system for

*M*.

#### Download:

06_16.pdf (revised August 2007).#### Published in:

*J. Symbolic Comp.*42 (2007) 1034-1051

(this appears in the special issue on

*Non-commutative Groebner Bases*, guest editor Viktor Levandovskyy, for papers by participants at the workshop

*Groebner Bases in Symbolic Analysis*, Special Semester on Groebner Bases and Related Methods, Hagenberg-Linz, Austria, May 8-17, 2006).