We present a version of the Knuth-Bendix string rewriting procedures
for group computations and apply it to the problem of computing the
module of identities among relators.
By lifting rewriting into the appropriate higher dimension we provide a
methodology which is alternative and complementary to the popular geometric
approach of pictures.
Reduction in ZG-modules with Applications to
Identities Among Relations
Abstract:
In this paper we describe methods for reducing sets of generators of
sub-ZG-modules, where G is a finite group.
The methods we describe utilise the procedures of saturation and
prefix reduction developed by Madlener and Reinert.
We apply the methods to the problem of reducing the
generating sets of the ZG-module obtained in the Brown-Razak construction
of a free crossed resolution of a group.
The reduction procedure we describe has been implemented and combined
with the implementation of the Brown-Razak construction,
so giving a program which will return a minimal set of
generators for the ZG-module of identities among relations for the
presentation P of a finite group.
One-sided Noncommutative Groebner Bases with Applications to
Coset Systems and Green's Relations
Abstract:
In this paper we describe methods of Groebner bases for one-sided ideals
in noncommutative algebras.
One-sided rewriting systems and their relations to the calculation of
one-sided ideals are considered.
We show that a complete one-sided rewrite system for a right congruence on a
semigroup S is equivalent to a Groebner basis for a right ideal in an
algebra K[S] (to some extent, this is already known).
In addition, the one-sided Knuth-Bendix algorithm is a special case of
the Buchberger algorithm (apparantly new).
In particular we observe the application that can be made to coset systems.
The paper concludes by showing how the noncommutative one-sided version
of the Buchberger algorithm can be applied to completable presentations
of semigroups to calculate Green's relations.
This paper contains introductory material on Petri-nets and
Groebner basis theory and makes some observations on the relation
between the two areas.
The aim of the paper is to give an outline of the two areas and
indicate the potential for the application of Groebner basis procedures
to problems involving Petri-nets.
Using rewriting systems to compute left Kan extensions
and induced actions of categories
Abstract:
The basic method of rewriting for words in a free monoid from given
relation data is extended to rewriting for paths in a free category
given Kan extension data.
This is related to work of Carmody-Walters on Todd-Coxeter for Kan extensions,
but allows for the output data to be infinite, described by a language.
The result also allows rewrite methods to be applied in a greater
range of situations and examples, in terms of induced actions of monoids,
categories, groups or groupoids.
Using Automata to obtain Regular Expressions for Induced Actions
Abstract:
Presentations of Kan extensions of category actions provide a natural
framework for expressing induced actions, and therefore
a range of different combinatorial problems. Rewrite systems for
Kan extensions have been defined and a variation on the Knuth-Bendix
completion procedure can be used to complete them -- when possible.
Regular languages and automata are a useful way of expressing sets and
actions, and in this paper we explain how to use rewrite systems for Kan
extensions to construct automata expressing the induced action and how
sets of normal forms can be calculated by obtaining language equations
from the automata.
Rewriting procedures generalise to Kan extensions of actions of categories
Abstract:
Kan extensions provide a natural general framework for a variety of
combinatorial problems.
We have developed rewriting procedures for Kan extensions
(over the category of sets) and this enables one program to address
a wide range of problems.
Thus it is possible to use the same framework (and therefore program)
to enumerate monoid or group (or category of groupoid) elements,
to enumerate cosets or congruence classes on monoids, calculate equivariant
equivalence relations, induced actions of groups,
monoids or categories and even more.
This extended abstract is an outline of
"Using Rewriting Systems to Compute Kan Extensions and
Induced Actions of Categories" by R. Brown and A. Heyworth.
