Mathematics Logo

U.W. Bangor - School of Informatics - Mathematics Preprints 1998



Computational Discrete Algebra

98.22 : HEYWORTH, A.

Rewriting as a special case of Groebner basis theory

Abstract:

Groebner basis theory is a branch of computer algebra which has been usefully applied to a wide range of problems. Kan extensions are a key concept of category theory capa\ble of expressing most algebraic structures. This paper combines the two, using Groebner basis techniques to compute certain kinds of Kan extension.

ftp access:

xxx archive: Postscript and source files

Published in:

Proc. CGAMA'98, Edinburgh 1998, C.U.P., London Math. Soc. lecture note series Vol.275 (2000).

98.23 : HEYWORTH, A.

Kan extensions, rewriting techniques, and Groebner bases

Summary:

This thesis concentrates on the development and application of Groebner bases methods to a range of combinatorial problems (involving groups, semigroups, categories, category actions, algebras and K-categories) and the use of rewriting for calculating Kan extensions.

The first chapter gives a short introduction to presentations, rewrite systems, and completion.

Chapter Two contains the most important result, which is the application of Knuth-Bendix procedures to Kan extensions, showing how rewriting provides a useful method for attempting to solve a variety of combinatorial problems which can be phrased in terms of Kan extensions. A GAP3 program for Kan extensions is included in the appendix.

Chapter Three shows that the standard Knuth-Bendix algorithm is step-for-step a special case of Buchberger's algorithm. The one-sided cases and higher dimensions are considered, and the relations between these are made precise. The standard noncommutative Groebner basis calculation may be expressed as a Kan extension over modules. A noncommutative Groebner bases program GAP3 has been written.

Chapter Four relates rewrite systems, Groebner bases and automata. Automata which only accept irreducibles, and automata which output reduced forms are discussed for presentations of Kan extensions. Reduction machines for rewrite systems are identified with standard output automata and the reduction machines devised for algebras are expressed as Petri nets.

Chapter Five uses the completion of a group rewriting system to algorithmically determine a contracting homotopy necessary in order to compute the set of generators for the module of identities among relations using the covering groupoid methods devised by Brown and Razak Salleh (98.24). (The resulting algorithm has been implemented in GAP3). Reducing the resulting set of submodule generators is identified as a Groebner basis problem.

ftp access:

heyworth.ps.gz gzipped postscript file.

Published in:

Proc. CGAMA'98, Edinburgh 1998, C.U.P., London Math. Soc. lecture note series Vol.275 (2000).

98.24 : BROWN, R. & RAZAK SALLEH, A.

Free crossed resolutions of groups and presentations of modules of identities among relations

Abstract:

We give general procedures for computing a small free crossed resolution of group, in terms of information such as a presentation. This yields for example methods for computing generators and relations for the module of identities among relations. The techniques of free crossed complexes, universal covers, and contracting homotopies lead to explicit formulae for higher syzygies.

Published in:

LMS JCM 2 (1999) 28-61.

School of Informatics: home page
Mathematics home page.
U.W.Bangor Home Page.
Latest modification to this page: 3/ 4/00