Skip to main content Skip to section menu

Computational Discrete Algebra


String-rewriting for double coset systems


In this paper we show how string-rewriting methods can be applied to give a new method of computing double cosets. Previous methods for double cosets were enumerative and thus restricted to finite examples. Rewriting methods do not suffer this restriction and we present some examples of infinite double coset systems which can now easily be solved using our approach. Automata provide the means for identifying expressions for normal forms in infinite situations and we show how they may be constructed in this setting. Further, related results on logged string-rewriting for monoid presentations are exploited to show how witnesses for the computations can be provided and how information about the subgroups and relations between them can be revealed. Finally, we briefly discuss how the double coset problem is a special case of a problem in computational category theory which indicates that the rewriting methods we describe are applicable to a much wider class of problem.

Revised as:


04.14 : EVANS, G.A.

Noncommutative Involutive Bases


Groebner Basis theory originated in the work of Buchberger and is now considered to be one of the most important and useful areas of computer algebra.
In 1993, Zharkov and Blinkov proposed an alternative method of computing a commutative Groebner Basis, namely the computation of an Involutive Basis.

In the mid 1980's, Mora showed that Buchberger's work could be generalised for noncommutative rings.
This article explores the issues surrounding the corresponding generalisation for Involutive Bases, and constructs a noncommutative involutive division which, when used with the noncommutative involutive basis algorithm, returns a noncommutative Groebner Basis on termination.

Published in:

Proc. 10th Int. Conf. Applications of Computer Algebra, ACA-2004, Beaumont, Texas,
Q.-N. Tran, editor, (2004) 49-64.


Site footer