|
University of Wales, Bangor - 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).