The information in this chapter refers to Version 3 of {\GAP}.
No attempt has been made yet to link t{\KBMAG} to Version 4.
This will hopefully happen eventually.
There are two ways in which this interface can be used.
In the first, files are read into {\GAP} that have been created externally.
A {\GAP} conversion function 'ReadRWS' has been provided for this purpose.
This function assumes that the name of the rewriting system (i.e. the left
hand side of the declaration contained in the file) is |_RWS|, so this
name should always be used for files that are to be accessed by {\GAP}.
The second only works currently for groups (since monoids do not yet
exists as a {\GAP} type). Documentation for this method can also be found as
a chapter in the {\GAP} manual in the 'gapdoc' directory of {\KBMAG}.
The applications of {\KBMAG} involving subgroups of groups; that is those
documented in Chapters "The Knuth--Bendix Program for Cosets of Subgroups", "The Automatic Coset System and Subgroup Presentation Package" and "Creating Subgroup Word Acceptors"
of this manual, have not yet been incorporated within the interface.
A finitely presented group, $G$ say, is first
defined within {\GAP}, and then the {\GAP} function 'FpGroupToRWS' is called
on $G$, and a corresponding rewriting system is returned.
It can be called with an optional boolean second-variable, for example
|R := FpGroupToRWS(G,true);|
in which case inverses of generators are
printed using a case-change convention. Otherwise, inverses are printed in
the usual way by appending the suffix |^-1| to the generator name.
Since the internal storage of rewriting-systems in particular is
different from the structure defined in the external file (for example,
words are stored internally as lists of integers), the user should not
attempt to create rewriting systems directly internally to {\GAP},
but should either read them in from external files, or create them using the
function 'FpGroupToRWS'.
An implementation of finitely presented monoids within {\GAP} is currently
being written, and this too will eventually have an interface with
rewriting-systems.
The library files in the directory called 'gap' contain elementary functions
for manipulating finite state automata and rewriting-systems.
Anyone who wishes to use these seriously, should look in the files 'fsa.g' and 'rws.g'. A finite state automaton must either be typed in
interactively, or (better) put into a file first, and read in. Of course,
the automatic group programs calculate finite state automata, and the
functions are probably mainly useful for playing with these. It important to
know that, before using any of the other {\GAP} functions on an automaton <fsa>,
the function 'InitializeFSA()' must be called. Some of the functions,
like those that count or enumerate the language of a finite state automaton,
perform the same operations as the corresponding standalone 'C'-programs,
but they will usually be much slower than the standalones. Nevertheless,
it is often convenient to be able to do such things without having to go
through the process of writing to file, running external program, and then
reading the answer back in.
After installing the package, but before starting to use the {\GAP} functions,
go into the {\GAP} directory and type 'makeinit'. This will create the
required 'init.g' file for the {\GAP} library.
This file should be read in from {\GAP} before using the functions.
The use of the library is best illustrated by providing a report of an
actual session, with comments interspersed.
The first example illustrates the use of 'kbprog' from {\GAP}.
First create the following external file called 'S3' (which, we shall assume
is in the directory |../kb_data|).
|
gap> Read("init.g");
gap> S3 := ReadRWS("../kb_data/S3");
#Reads in the file, and converts it to an internal rewriting-system.
#However, it is still displayed as in the external file!
rec(
isRWS := true,
generatorOrder := [a,b],
inverses := [a,b],
ordering := "shortlex",
equations := [
[b*a*b,a*b*a]
]
)
gap> #Now we run the Knuth-Bendix program using the function 'KB', which
gap> #calls the external program "kbprog".
gap> KB(S3);
#System is confluent.
#Halting with 3 equations.
true
gap> #S3 now contains the confluent set of equations.
gap> S3;
rec (
isRWS := true,
isConfluent := true,
ordering := "shortlex",
generatorOrder := [a,b],
inverses := [a,b],
equations := [
[a^2,IdWord],
[b^2,IdWord],
[b*a*b,a*b*a]
]
)
gap> #Now we can do some word-reductions.
gap> ReduceWordRWS(S3,(a*b)^3);
IdWord
gap> ReduceWordRWS(S3,a*b*a);
a*b*a
gap> ReduceWordRWS(S3,b*a*b*a);
a*b
gap> SizeRWS(S3);
6
gap> EnumerateRWS(S3,0,5);
[ IdWord, a, a*b, a*b*a, b, b*a ]
|
The next example illustrates the use of the automatic group package from {\GAP}.
This example is not quite so trivial as the preceding one. The group is the
fundamental group of the complement of the Borromean rings, which is a
three-dimensional hyperbolic manifold. The word-acceptor was used to enumerate
the words of length up to 4. This was used to speed up the calculations
required for drawing views of a tessellation of hyperbolic space by regular
dodecahedra, which can be seen in the video ``Not Knot\'\'.
First make the following file, called |BR| (in the directory |../ag_data|).
|
_RWS := rec(
isRWS := true,
ordering := "shortlex",
generatorOrder := [a,A,b,B,c,C,d,D,e,E,f,F],
inverses := [A,a,B,b,C,c,D,d,E,e,F,f],
equations := [
[a*a*a*a,IdWord], [b*b*b*b,IdWord], [c*c*c*c,IdWord],
[d*d*d*d,IdWord], [e*e*e*e,IdWord], [f*f*f*f,IdWord],
[a*b*A*e,IdWord], [b*c*B*f,IdWord], [c*d*C*a,IdWord],
[d*e*D*b,IdWord], [e*f*E*c,IdWord], [f*a*F*d,IdWord]
]
);
|
gap> #Finally, let\'s see how many words there are of different lengths.
gap> for ct in [0..6] do
> Print(SizeEnumerateRWS(BR,ct,ct),"\n");
> od;
1
12
102
812
6402
50412
396902
gap> quit;
|
{\bf UPDATE}\:\ It is now possible to install
{\KBMAG} as a share-libraryin Version 3 of {\GAP}.
Instructions for this are in the 'README' file in
the main {\KBMAG} directory.
{\bf NEW}\:\ The file 'wordorder.g' written by Sarah Rees contains some
experimental routines for finding the automatic structure of groups using
orderings other than short-lex, such as weighted lex, and inverse-pair
wreath product. There is currently at least one bug in this, in that
they will not complete successfully if a generator reduces (under
this ordering) to a word of length greater than one. The interested
user is advised to seek help by e-mail!
¤ Dauer der Verarbeitung: 0.14 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
