Readers interested in such matters should note that MAF does not deal with semigroups. It is a trivial operation to convert a semigroup into corresponding monoid, and equally trivial to convert the automata MAF produces for such a monoid into automata for the original semigroup. If support for semigroups is desired it will be easy to add.
Most of the computations to be described in this section are usually performed by invoking MAF's principal utility: automata.
In order for MAF to be able to perform computations on a group or monoid, it must first be supplied with an appropriate presentation, in the form of a text file containing a standard GASP format rewriting system. A file in this format will generally be called simply an input file in this document.
Although the MAF user will probably think of an input file as a presentation it is important to remember that there are some differences from a group presentation:
An informal definition of the syntax of input files syntax can be found in MAF Reference : Input files. The various options for ordering words are discussed in MAF Reference : Word-ordering methods.
Readers who have not already done so, and who have not previously used KBMAG, should refer to MAF Tutorial 1: Processing an input file before continuing.
Once an input file has been created, one may need to decide what kind of a solution to the word problem MAF should look for. The good news is that in many cases this is unnecessary. However, it is important that the user should be aware of the issues, because otherwise MAF may run in an inefficient manner. The various possibilities are discussed more fully in Overview: Solutions to the word problem. automata will attempt to construct either a finite confluent rewriting system, or an automatic structure (or very likely both). In either case the computation usually uses the Knuth-Bendix procedure. An alternative, for input files describing a finite group, is to attempt to use coset enumeration to find the coset table of the group.
Not all input files have a finite confluent rewriting system, and many infinite groups and monoids may not have a finite confluent rewriting system for any choice of generating set and reduction ordering. The existence of a finite confluent rewriting system for any particular choice of generating set and word-ordering does not guarantee its existence for any other choice.
Not all groups have automatic structures. There are infinite groups, with a solvable word problem, for which it is possible to show that no such structure can exist. If a group does have an automatic structure then the group is called an "automatic group". In principle, the existence of an automatic structure for some choice of generating set does guarantee the existence of one for any other finite generating set; this is why it is meaningful to talk of a group's being automatic. An algorithm exists for constructing an automatic structure on an arbitrary finite set of generators given any particular automatic structure. MAF is only able to find automatic structures that are natural for the chosen generating set and word-ordering: ones in which the accepted word for each element is the least word in the word-ordering that is equal to it as a group element. However, if you have succeeded in computing an automatic structure using some generating set, MAF is able to compute a word acceptor for any other genererating set using the utility gpxlatwa.
It will be useful, informally, to speak of an input file as being automatic or confluent, where by this the terms are understood to mean, "MAF can compute an automatic structure from the input file" and "MAF can compute a finite confluent rewriting system from the input file". This makes it easier to state an important fact: an input file can be either, neither, or both of these. MAF's ability to find either type of structure for a group is heavily dependent on the choice of presentation and word-ordering (a first hint of this can be found by referring to MAF Tutorials: 2 - Choosing generators). So, given a presentation for an unknown group, one is immediately faced with the dilemma of which kind of structure to look for. This dilemma does not as occur for monoids, since MAF cannot construct automatic structures for them.
A major difference between MAF and KBMAG from the point of view of a user hoping to find a solution to the word problem for a particular group, is that with KBMAG one has to decide in advance, whether to look for an automatic structure, or for a confluent rewriting system. In MAF the situation is different: MAF's default behaviour, usually, is to look for both at the same time. This is not always the advantage it might seem to be - it might sometimes be better to run two copies of automata independently, one looking for an automatic structure, the other for a confluent rewriting system. Also, in some cases, it will quickly become apparent to the user that there is little or no hope of finding an automatic structure. In such cases it is usually much better to interrupt automata, and to start it again with an option which tells it only to look for a confluent rewriting system.
MAF has no means of knowing in advance whether its computations will succeed (no such means can exist), and it will run for ever until they do, unless interrupted, or it gives up due to limits placed on it being exceeded, or insufficient resources are available for it to continue.
The user can supply various command line options, which will control what automata MAF searches for, and when they are searched for. These may be termed goal setting options. We shall introduce the most important of these now. Refer to MAF Reference (Usage): automata for more complete information on all the many command line options accepted by automata.
There are two command line options for doing this: -no_wd and -confluent. The options only differ in what happens when MAF does succeed in finding a confluent rewriting system. With the first option, this is the only structure that MAF will compute and output. With the second option, MAF will then attempt to compute an automatic structure as well, using a word-acceptor computed from the rewriting system as the basis of the structure. Both these options may substantially speed up processing, and do usually do so if the input file presents a finite group. The -confluent option is on by default if the input file uses a word-ordering for which the construction of automatic structures is difficult. For large finite groups automatic structures can require a lot of computation, and the confluent rewriting system will usually be more useful in practice, and so the -no_wd option is often used with such groups.
The -no_kb option tells MAF not to use the Knuth-Bendix procedure, and instead to attempt to construct an automatic structure immediately, using only the equations contained in the input file, and any others that are readily deducible from them. For infinite automatic groups this option often produces the fastest results, even for some groups for which the construction of the automatic structure is quite difficult. However, it can happen that MAF has great difficulty in building trial automatic structures. In such cases it may be best to run automata without this option, to allow more word-differences to be discovered first (though for the most difficult automatic groups it is often the case that there is almost no hope of running Knuth-Bendix for long enough to avoid this difficulty - it is very difficult to know when all the word-differences have been discovered). The -no_kb option is disastrous if the presentation is actually a difficult presentation of a finite group. MAF will usually eventually be able to discover this, but it will take much longer than it would have done had the Knuth-Bendix procedure been used. If a group is finite MAF will insist on finding the confluent rewriting system that certainly exists before it computes the automatic structure.
MAF's default behaviour is to search for an automatic structure only when an input file for a group uses a geodesic word-ordering (i.e. a word-ordering where a word is always greater than any shorter word). To make MAF search for an automatic structure for a word-ordering such as wtlex then one can use either of two options: -wd or -force_differences. The behaviour of the latter option is described in the next section. The -wd option will cause MAF to search for word-differences with its default strategy, in which equations with word-differences are favoured only until there are 5000 word-differences or so.
The -force_differences command line option will ensure that MAF computes word-differences if it is possible to do so, and will not stop favouring equations that contain new word-differences if the number of word-differences is high. One can run automata like this for a minute or two to help decide on the best strategy. If the number of word differences increases rapidly, and soon exceeds 5000, then there is little or no hope that MAF will be able to compute an automatic structure. In such cases it is best to stop automata and to restart it with the -confluent or -no_wd options. If, on the other hand, the number of word differences has stopped increasing rapidly by this time, then there is a good chance that the -no_kb option will give the fastest results. Start a second copy of automata, specifying the -no_kb option, this time leaving the first copy running, and wait until one of them succeeds. If memory becomes short then stop whichever seems to be making less progress.
It is perfectly possible for an input file to have a provably correct word-acceptor which does not form part of an automatic structure. This will happen, for example, whenever there is a finite confluent rewriting system for the input file, but the number of word-differences is not finite. It may also happen that while the minimal confluent rewriting system is not finite, there are only a finite number of word-differences for it, so that the equations that appear in it can be recognised by an automaton. In such cases one can construct a word-acceptor, even if it is not possible to construct the general multiplier because that requires an infinite number of word-differences. This situation does sometimes arise in practice. MAF can find such word-acceptors but cannot prove them correct.
MAF prefers, whenever possible, to compute the word-acceptor for an input file from a confluent rewriting system, rather than from a word-difference machine. It is worth having a word-acceptor even when a confluent rewriting system exists, because although both structures can be used to enumerate the reduced word for each element of the group, the former will usually have many fewer states, and use much less memory. For largish finite groups it is often very difficult, if possible at all, to construct a word-acceptor from the word-difference machine, because there are too many word-differences, whereas the computation of the word-acceptor from a confluent rewriting system is very rapid. Usually, though not always, MAF refrains from trying to build an automatic structure prior to a rewriting system becoming confluent, in the case that it will do so, because such groups usually have many word-differences.
MAF has a very large number of command line options that modify the behaviour of its Knuth-Bendix implementation. These are all documented in Usage: automata. It is quite difficult to remember how to use all of these various options, so to make life simpler the -strategy string option is provided. This can select one from a range predefined strategies for MAF to follow, and also apply modifications to the chosen strategy. One should do this only if the strategy MAF selects when no specific command line options are given does not seem to work well: some of the strategy options have very bad behaviour with many input files, whereas the automatically chosen strategy MAF will usually work reasonably well, even if it is not necessarily the fastest possible for that particular input file. The various strategies, and the combination of other options that they select are described in detail in Usage: automata, but the most important of the strategies are introduced here:
First come three strategies that are not normally specified explicitly, but which are nevertheless important; they select combinations of options that MAF commonly uses in particular scenarios:
Note that MAF does not actually select any of these options as its "default strategy", because the "strategy" option does not actually exist internally, and nor do these options. However, if no specific command line options are chosen, the internal options that MAF really does use in those scenarios would be set to the same values, or at least very similar ones, as these specific strategy options select. The reason why you might want to specify one of these options specifically is that you can use "strategy modifiers" as a way to investigate whether a minor modification to the default strategy might work better for a particular input file.
Next we mention some strategy options that may sometimes be useful:
-strategy long and -strategy era are important strategies, because one of them may be the only strategy that works well with some input files. Unfortunately MAF is not able to determine for itself when an input file is going to have this unfortunate property, and neither strategy works well the majority of the time, so MAF never works like this by default. If an input file does work well with either of these strategies it is rather likely that KBMAG will process the file as it stands more efficiently than MAF. It is also likely that MAF will be able to process the file much faster than that, and using a default strategy, if the word-ordering method is changed to "recursive" or a similar wreath product ordering. An input file has a good chance of running more quickly with one or other of these strategies if most of the following conditions apply:
"shortlex".
-strategy quick and -strategy easy turn off some of the additional processing MAF normally performs. As a result some input files will be processed more quickly if one of these two options is used. On the other hand, for some input files these strategies will take much longer than the default strategy, and it is impossible to know for sure which strategy without trying all of them.
The progress messages usually output by automata are not there just to let you know that automata has not hung. They contain information which may help you to decide whether the options that are being used are good.
For finite groups, but not monoids, there is a third possibility for finding a solution to the word problem: instead of using the Knuth-Bendix procedure one can use coset enumeration. If it is possible to enumerate the cosets of the trivial group, then the standardised coset table provides an effective solution to the word problem. On average, and when it works well, computing a coset table using coset enumeration is significantly faster than computing a confluent rewriting system using the Knuth-Bendix procedure, and the coset table may well require less memory than a confluent rewriting system and index automaton. More information about MAF's coset enumerator gptcenum can be found in the relevant section of MAF Reference: RWS Utilities.
For difficult presentations, automata is very often far superior in performance, both in execution time, and the amount of memory required. On the other hand, for presentations of very large finite objects with very large confluent rewriting systems gptcenum is likely to be much better than automata. It is certainly worth experimenting with both programs.
As usually implemented by MAF the algorithm used to construct an automatic structure is theoretically incomplete. When MAF creates an automatic structure for a group it checks that it defines a closed multiplication on the language of the word-acceptor, but it does not check that the multiplication is associative, nor that it actually satisfies the group axioms. In theory MAF should perform some checks to ensure the proposed automatic structure really does define a group multiplication that satisfies the axioms. There is a good reason why it does not do so: the checks frequently take much longer to perform than constructing the automatic structure takes in the first place, and they have never been known to fail (for a group automatic structure). It is possible to make these checks using MAF, either by supplying a command line option when automata is invoked, or by running a separate axiom checking program afterwards. The first approach is usually faster, the second approach marginally safer, because more memory will be available if the automatic structure is checked later on by a separate utility.
automata checks the axioms for the automatic structure if the command line option -validate is specified. KBMAG users may like to note that this option is automatically supplied if the MAF version of autgroup is used to build an automatic structure instead of automata.
The separate utility for checking axioms is called gpaxioms; it is described in Usage information for RWS Utilities.
MAF does check the axioms by default when an automatic structure for a coset system is built, because for coset systems the checks can sometimes fail.
In this section, we mention some of the example input files, all to be found in various subfolders of the examples folder. These can usefully be used as test examples, and some of them have been included to demonstrate particular features.
The input files in trivial are all presentations of the trivial group. Note, in particular, degen4a, degen4b and degen4c. These are the first three of an infinite sequences of increasingly complicated presentations of the trivial group, due to B.H. Neumann. automata will run very quickly on all of these presentations, whereas KBMAG can only do the first two within a reasonable time. The -confluent, or the -nowd command line options speed up the calculation considerably in the case of degen4c, the primary reason for this being that automata computation of word-differences is very time consuming for this presentation. The fastest results for degen4c can perhaps be obtained by changing the word-ordering to "recursive" and using the command line options -strategy easy -work_order 4: when these two options are used the computation takes only one second!. For shortlex -strategy easy/i -work_order 6 is equally fast.
The input files in automatic are all for automatic groups. Most of the examples in this folder are of at least moderate difficulty and most run much faster with the -nokb option than without. Easier examples are to be found in the hyperbolic and coxeter folders. The most difficult input files for automatic groups are to be found in the hard folder - all those examples require several hours at least.
The example subgroups/ab2 is the free abelian group on two generators, as is subgroups/ab2_abAB. The former, which has generatorOrder := [a,A,b,B] has a finite confluent rewriting system. The latter, which has generatorOrder := [a,b,A,B], does not. It is almost always best to order the alphabet so that generators and their inverses appear next to one another if they are different.
The monoids directory contains a number of monoids. a4monoid illustrates what might happen if the inverses field is omitted or not set up. What would be a group of order 12 as a group presentation, becomes an infinite monoid. Several of the examples in this folder are related to the Fibonacci groups. Others are monoid presentations, where generators are not supplied with inverses. Try f25monoid, which is the presentation of the Fibonacci group F(2,5), but as a monoid. In fact, the structure is almost identical to the group in this example. The group is cyclic of order 11. The monoid has order 12, the extra element being either the a^11 word (which is not recognised as being equal to IdWord), or IdWord itself. The corresponding semigroup (without the empty IdWord) is isomorphic to the group. f27monoid and f27monoid_shortlex are both monoid presentations corresponding to the Fibonacci group F(2,7), which has order 29. As before the monoid has one extra element, which in this case is a^29. This example is another interesting example of the differences between MAF and KBMAG. KBMAG cannot easily solve this example when shortlex ordering is used, but with MAF it completes in around 5 seconds with the default strategy, and in similar times with some but not all of the other predefined strategies. With this example it is important to allow "special overlap" processing, and to use an "open" strategy that makes use of new equations as soon as possible. Particularly bad results are obtained if -strategy era is used. For f27monoid, which uses "recursive" ordering KBMAG's "maxstoredlen" option is set in the input file. However, the values specified for this option could not possibly work with MAF, because several of the equations in the confluent set exceed the rhs limit. MAF ignores this KBMAG specific option, and, with no limits on equation length, completes almost instantly. Use of the "pool" is crucial to MAF's success for this and most other input files using a wreath product word-ordering.
In the hyperbolic folder there are many hyperbolic examples of Von Dyck and triangle groups. All the groups are automatic for any choice of generating set, and it would seem that all of them have finite confluent rewriting systems as well, but not all have them for "shortlex" word-ordering. The rule seems to be that all the triangle groups have a finite "shortlex" rewriting system, but the Von Dyck groups only have them when exactly one of the 3 numbers representing the angles of the triangle is even, when the natural 3 generator presentation must be used. All the Von Dyck groups seem to be confluent on a 2 generator presentation using "recursive" ordering. These groups are amongst those discussed in a paper of Le Chenadec from 1986 entitled "Complete group presentations", but the author has not investigated whether the confluent rewriting systems found by MAF are the same as the ones in that paper.
In the pathological folder there are a large number of input files that are all for the same group : #8 in the list of presentations of groups of order 38 given in "Groups of Deficiency Zero". The files vary only in the word-ordering except that in some cases the relators have been reversed. Some of these can be processed quickly, while others seems to be hopeless cases, and a wide range of unpleasant behaviours can be
observed. For instance with "rt_recursive" ordering the input file can currently be processed fairly quickly with generatorOrder=[A,a,B,b,C,c] but not with generatorOrder=[a,A,b,B,b,c,C]. Many of these files seem extremely sensitive to minor code changes in MAF, or work well only when the command line options are carefully chosen.
In the recursive subfolder there are more examples using the "recursive" word-ordering For nilp2, nonhopf, heinnilp and verifynilp, a wreath product word-ordering is essential. (These examples also work if they are changed to use an ordering where each generator is at the same level as its inverse. The author has never come across an input file where this is not the case). All these examples are from KBMAG. The last two of these are examples of the use of Knuth-Bendix to prove that a presentation defines a nilpotent group. The verifynilp again show the same difference in behaviour from KBMAG as did f27monoidexample. In KBMAG the maxstoredlen parameter (or equivalently the -mrl option) is used to make kbprog complete more quickly for some examples. MAF has to ignore this setting, because in every one of the examples included with KBMAG that use such a setting, the KBMAG value of the setting prevents MAF from ever finding the correct confluent rewriting system, whereas when the setting is ignored MAF very quickly completes successfully! MAF does allow for such a setting however, in case it should ever prove useful: MAF's equivalent of KBMAG's maxstoredlen is maf_maxstoredlen. However, the author has yet to find a single example where the use of this setting is at all beneficial. In most cases it just prevents MAF from ever finding a confluent set.