|
University of Wales, Bangor - Mathematics Preprints 2005
Computational Discrete Algebra
|
|
|
05.07 :
BROWN, R., GHANI, N., HEYWORTH, A. & WENSLEY, C.D.
String rewriting for double coset systems
(revision of preprint 04.04)
Summary:
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.
Our 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.
Even when both enumerative and rewriting techniques are present,
our rewriting methods will be competitive because they
i) do not require the preliminary calculation of cosets;
and ii) as with single coset problems, there are many examples
for which rewriting is more effective than enumeration.
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 the relations between them can be extracted.
Finally, we discuss how the double coset problem
is a special case of the problem of computing induced actions of categories
which demonstrates that our rewriting methods are applicable
to a much wider class of problems than just the double coset problem.
Download:
Published in:
J. Symbolic Comp.
41 (2006) 573-590.
05.18 :
EVANS, G.A.
Noncommutative Involutive Bases
Summary:
The theory of Gröbner Bases originated in the work of Buchberger
and is now considered to be one of the most important and useful areas
of symbolic computation.
A great deal of effort has been put into improving Buchberger's algorithm
for computing a Gröbner Basis,
and indeed in finding alternative methods of computing Gröbner Bases.
Two of these methods include the Gröbner Walk method
and the computation of Involutive Bases.
By the mid 1980's, Buchberger's work had been generalised
for noncommutative polynomial rings by Bergman and Mora.
This thesis provides the corresponding generalisation
for Involutive Bases and (to a lesser extent) the Gröbner Walk,
with the main results being as follows.
-
Algorithms for several new noncommutative involutive divisions are
given, including strong; weak; global and local divisions.
-
An algorithm for computing a noncommutative Involutive Basis is given.
When used with one of the aforementioned involutive divisions,
it is shown that this algorithm
returns a noncommutative Gröbner Basis on termination.
-
An algorithm for a noncommutative Gröbner Walk is given,
in the case of conversion between two harmonious monomial orderings.
It is shown that this algorithm generalises
to give an algorithm for performing a noncommutative Involutive Walk,
again in the case of conversion between two harmonious monomial orderings.
-
Two new properties of commutative involutive divisions are introduced
(stability and extendibility),
respectively ensuring the termination of the Involutive Basis algorithm
and the applicability (under certain conditions) of homogeneous methods
of computing Involutive Bases.
Source code for an initial implementation of an algorithm to compute
noncommutative Involutive Bases is provided in Appendix B.
This source code, written using ANSI C and
a series of libraries (AlgLib) provided by MSSRC,
forms part of a larger collection of programs
providing examples for the thesis,
including implementations of the commutative
and noncommutative Gröbner Basis algorithms;
the commutative Involutive Basis algorithm
for the Pommaret and Janet involutive divisions;
and the Knuth-Bendix critical pairs completion algorithm
for monoid rewrite systems.
Published in:
University of Wales, Bangor, PhD thesis (September 2005)
Download:
- evans.pdf
(This pdf file, created from LaTeX source, uses the hyperref package
to provide document navigation tools such as bookmarks and clickable links
for various items including citations, page numbers and algorithms.)
-
arXiv :
math.RA/0602140