README.md
1[](https://travis-ci.org/gap-packages/kbmag)
2[](https://codecov.io/gh/gap-packages/kbmag)
3
4# The GAP 4 package 'KBMAG'
5
6This package uses external binaries and currently works only under
7UNIX/LINUX systems.
8
9
10## Package description
11
12KBMAG (pronounced `Kay-bee-mag`) stands for `Knuth-Bendix on Monoids, and
13Automatic Groups`. It is a stand-alone package written in C, for use under
14UNIX, with an interface to GAP. There are interfaces for the use of KBMAG with
15finitely presented groups, monoids and semigroups defined within GAP. The
16package also contains a collection of routines for manipulating finite state
17automata, which can be accessed via the GAP interface.
18
19The overall objective of KBMAG is to construct a normal form for the elements
20of a finitely presented group G in terms of the given generators together with
21a word reduction algorithm for calculating the normal form representation of
22an element in G, given as a word in the generators. If this can be achieved,
23then it is also possible to enumerate the words in normal form up to a given
24length, and to determine the order of the group, by counting the number of
25words in normal form. In most serious applications, this will be infinite,
26since finite groups are (with some exceptions) usually handled better by
27Todd-Coxeter related methods. In fact a finite state automaton W is calculated
28that accepts precisely the language of words in the group generators that are
29in normal form, and W is used for the enumeration and counting functions. It
30is possible to inspect W directly if required; for example, it is often
31possible to use W to determine whether an element in G has finite or infinite
32order.
33
34The normal form for an element g in G is defined to be the least word in the
35group generators (and their inverses) that represents G, with respect to a
36specified ordering on the set of all words in the group generators.
37
38KBMAG offers two possible means of achieving these objectives. The first is to
39apply the Knuth-Bendix algorithm to the group presentation, with one of the
40available orderings on words, and hope that the algorithm will complete with a
41finite confluent presentation. (If the group is finite, then it is guaranteed
42to complete eventually but, like the Todd-Coxeter procedure, it may take a
43long time, or require more space than is available.) The second is to use the
44automatic group program. This also uses the Knuth-Bendix procedure as one
45component of the algorithm, but it aims to compute certain finite state
46automata rather than to obtain a finite confluent rewriting system, and it
47completes successfully on many examples for which such a finite system does
48not exist. In the current implementation, its use is restricted to the
49shortlex ordering on words. That is, words are ordered first by increasing
50length, and then words of equal length are ordered lexicographically, using
51the specified ordering of the generators.
52
53The GAP4 version of KBMAG also offers extensive facilities for finding
54confluent presentations and finding automatic structures relative to a
55specified finitely generated subgroup of the group G. Finally, there is a
56collection of functions for manipulating finite state automata that may be of
57independent interest.
58
59
60## Installation
61
62This package uses external binaries and currently works only under
63UNIX/LINUX systems.
64
65It will work only on GAP versions >= 4.7.
66
67To complete the installation of the `kbmag` package go to the
68directory `kbmag` created (the directory contains a copy of this
69README file) and call
70
71 ./configure <PATH>
72
73where `PATH` is a path to the main GAP root directory; so normally you
74would call
75
76 ./configure ../..
77
78and then call
79
80 make
81
82to compile the binary.
83
84If you installed GAP on several architectures, you must execute this
85configure/make step for the `kbmag` package on each of the architectures
86immediately after configuring GAP itself on this architecture.
87
88
89## Documentation
90
91Full information and documentation can be found in the manual, available
92as PDF `doc/manual.pdf` or as HTML `doc/chap0.html`, or on the package
93homepage at
94
95 <https://gap-packages.github.io/kbmag/>
96
97
98## Bug reports and feature requests
99
100Please submit bug reports and feature requests via our GitHub issue tracker:
101
102 <https://github.com/gap-packages/kbmag/issues>
103
104
105## License
106
107kbmag is free software; you can redistribute it and/or modify
108it under the terms of the GNU General Public License as published by
109the Free Software Foundation; either version 2 of the License, or
110(at your option) any later version.
111
112For details see the file LICENSE.
113
){kind=link}
){kind=link}