KBMAG (pronounced ``Kay-bee-mag'') stands for Knuth--Bendix on
Monoids, and Automatic Groups. It is a stand-alone package written
in C, for use under UNIX, with an interface to GAP. This chapter
describes its use as an external share library from within GAP.
The current interface is restricted to finitely presented groups.
Interfaces for the use of KBMAG with monoids and semigroups will be
released as soon as these categories exist as established types
inGAP.
To use this package effectively, some knowledge of the underlying theory and algorithms is advisable. The Knuth-Bendix algorithm is described in various places in the literature. Good general references that deal with the applications to groups and monoids are LeC86 and the first few chapters of Sims94. For the theory of automatic groups see the multi-author book ECHLPT92. The algorithms employed by KBMAG are described more specifically in EHR91 and Holt94.
The manual for the stand-alone KBMAG package (which can be found in
the doc directory of the package) provides more detailed information
on the external C programs that are called from GAP. The
stand-alone also includes a number of general programs for
manipulating finite state automata, which could easily be made
accessible from GAP. This, and other possible extensions, such as
the provision of more orderings on words, may be made in the future,
depending to some extent on user-demand.
The overall objective of KBMAG is to construct a normal form for the elements of a finitely presented group G in terms of the given generators, together with a word reduction algorithm for calculating the normal form representation of an element in G, given as a word in the generators. If this can be achieved, then it is also possible to enumerate the words in normal form up to a given length, and to determine the order of the group, by counting the number of words in normal form. In most serious applications, this will be infinite, since finite groups are (with some exceptions) usually handled better by Todd-Coxeter related methods. In fact a finite state automaton W is calculated that accepts precisely the language of words in the group generators that are in normal form, and W is used for the enumeration and counting functions. It is possible to inspect W directly if required; for example, it is often possible to use W to determine whether an element in G has finite or infinite order. (See Example 4 below.)
The normal form for an element g in G is defined to be the least word in the group generators (and their inverses) that represents G, with respect to a specified ordering on the set of all words in the Setting the ordering below.
KBMAG offers two possible means of achieving these objectives. The first is to apply the Knuth-Bendix algorithm to the group presentation, with one of the available orderings on words, and hope that the algorithm will complete with a finite confluent presentation. (If the group is finite, then it is guaranteed to complete eventually but, like the Todd-Coxeter procedure, it may take a long time, or require more space than is available.) The second is to use the automatic group program. This also uses the Knuth-Bendix procedure as one component of the algorithm, but it aims to compute certain finite state automata rather than to obtain a finite confluent rewriting system, and it completes successfully on many examples for which such a finite system does not exist. In the current implementation, its use is restricted to the shortlex ordering on words. That is, words are ordered first by increasing length, and then words of equal length are ordered lexicographically, using the specified ordering of the generators.
For both of the above procedures, the first step is to create a GAP record known as a em rewriting system R from the finitely presented group G. Some of the fields of this record can be used to specify the input parameters for the external programs, such as the ordering on words to be used by the Knuth-Bendix procedure. One of the two external programs is then run on R. If successful, it updates some of the fields of R, which can then be used to reduce words in the group generators to normal form, and to count and enumerate the words in normal form.
In fact, the relationship of a rewriting system to that of the group from which it is constructed is in many ways similar to that between a Presentation Record and its associated finitely presented group, as described in Presentation Records. In particular, the rewriting rules, which can be thought of as (a highly redundant) set of defining relations for the group, can be changed, whereas the defining relators of a finitely presented group cannot be altered without effectively changing the group itself.
In the descriptions of the functions that follow, it is important to distinguish between irreducible words, and words in normal form. As already stated, a word is in normal form if it is the least word under the ordering of the rewriting system that defines a particular group element. So there is always a unique word in normal form for each group element, and it is determined by the group generators and the ordering on words in the group generators. A word in a rewriting system is said to be irreducible if it does not contain the left hand side of any of the reduction rules in the system as a subword. Words in normal form are always irreducible, but the converse is true if and only if the rewriting system is confluent. The automatic groups programs provide a method of reducing words to normal form without obtaining a finite confluent rewriting system (which may not even exist).
Diagnostic output from the GAP procedures can be turned on by
setting the global variable InfoRWS to Print. Diagnostic output
from the external programs is controlled by setting the silent,
Control parameters below.
GAP 3.4.4