Skip to main content Skip to section menu

Mathematics Preprints 1999



Computational Discrete Algebra


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

Logged rewriting and identities among relators

Abstract:

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.

Published in:

Groups St Andrews 2001 in Oxford, London Math. Soc. Lecture Note Series 304,
eds. C.M. Campbell, E.F. Robertson & G.C. Smith, Cambridge Univ. Press (2003) 256-276.


99.09 : HEYWORTH, A. & REINERT, B.

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.

Published in:


99.10 : HEYWORTH, A.

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.

Published in:


99.11 : CHANDLER A. & HEYWORTH, A.

On noncommutative Groebner bases and Petri-nets

Abstract:

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.

Published in:


99.14 : BROWN, R. & HEYWORTH, A.

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.

Published in:

J. Symbolic Computation 29 (2000) 5-31.

xxx archive link math.CO/9903032


99.19 : HEYWORTH, A.

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.

Published in:


99.39 : HEYWORTH, A.

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.

Published in:

Proc. FLoC/RTA'99 (1999)

ftp access:

xxx archive


Site footer