Skip to main content Skip to section menu

Mathematics Preprints 2006

Computational Discrete Algebra

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

IdRel 2.02 : a deposited share package for GAP


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


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


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


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.



Published in:

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

Complete involutive rewriting systems


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.


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).

Site footer