This manual will adjust its width on screen according to the size of the browser window. If you are using a down-level browser such as IE6 or below this may result in the text being unpleasantly wide on a PC screen. You may find it easier to read if you adjust your browser window to the most comfortable reading size.
MAF (pronounced to rhyme with Taff) stands for Monoid Automata Factory. MAF is a software package that attempts to compute automata representing the structure of a group or monoid, (or of a subgroup of a group), based on input containing a suitable presentation, which is supplied in the form of a rewriting system. MAF is a re-implementation and extension, in C++, of Derek Holt's package KBMAG. Most programs from KBMAG have direct replacements in MAF that are very similar and largely compatible. By virtue of its compatibility with KBMAG, MAF components can be used to replace at least some of the binary components of the KBMAG GAP package and are therefore usable from within the GAP system. This is covered very briefly at the end of this document in Using MAF from within GAP.
Readers who are C++ programmers may like to note that all the functionality of MAF is available through a C++ library, which may be useful for programs that need to generate such automata dynamically - for example programs that draw Kleinian Limit sets or pictures of hyperbolic tessellations.
The purpose of this document is to provide instructions for MAF's use as a stand-alone package, and it presumes that the reader is already familiar with at least basic group theory, and has a general understanding of rewriting systems and finite state automata.
You can download the binaries and source code of MAF by visiting the MAF website on SourceForge, or the MAF project on SourceForge (Downloads are no longer available from the authors personal web site).
As most people who are likely to be interested in MAF will previously have used KBMAG the next section briefly compares the two packages. If you are familiar with KBMAG you should be able to use MAF straight away. However, please remember that to gain access to most of the new functionality you need to use a new program: automata, rather than one of the programs that emulates a corresponding KBMAG program. If you have not used KBMAG before then you can omit the next section and read the Overview.
There are work-alike programs with the same names for all of the main KBMAG programs: kbprog, autgroup, kbprogcos, autcos (amongst others). If the KBMAG versions are replaced by the corresponding MAF programs, the GAP KBMAG package works.
In terms of facilities, the two main new facilities are:
MAF succeeds on many examples where KBMAG either fails, or requires a very careful selection of options to succeed. In particular, MAF will usually work better with recursive orderings.
For very difficult rewriting systems, MAF is more likely to succeed more quickly, provided plenty of memory is available. For example the degen4c example (a famous presentation of the trivial group using three relators of length 125) can be solved in about 20 seconds or less on a modern PC. MAF tends also to be much quicker than KBMAG when processing rewriting systems for large finite groups that are otherwise not particularly difficult. For example it can find confluent rewriting systems for groups of orders of a million or so in around two or three minutes even when the confluent rewriting system may have up to a million or so equations. It is however the case that MAF has fewer options for limiting its memory use than KBMAG, and uses memory less conservatively in any case. MAF may not yet be a good choice when there are very long relators, or very many generators (though it now works well with presentations that have several hundred generators).
For some rewriting systems MAF may take longer to complete than KBMAG. This is partly because because it sometimes computes more automata, but mainly because it uses a different kind of criterion to determine when it should stop Knuth Bendix expansion. For example there is one coset system which KBMAG solves almost instantly, but which takes about 40 seconds using MAF, unless you suppply a certain command line option, in which case it completes in under 2 seconds. For "difficult" presentations, it may sometimes happen that KBMAG is "lucky" when MAF is not.
Although MAF is highly configurable, most of the time you should not have to give it any special options in order to solve a problem. While the programs that emulate KBMAG programs accept most of their command line and configuration options, many of them are ignored. MAFs "real" configuration options are often different from anything in KBMAG.
The algorithms employed in MAF are all based on those in the KBMAG package, but many changes have been made, which it is hoped are improvements. Some of these are described in How MAF Works .
The applications of MAF can be divided into three inter-relating categories. These are covered in detail in the later sections: MAF for Groups and Monoids, and MAF for Subgroups and Cosets, MAF Finite State Automata Utilities but they are summarised here.
Firstly, MAF can be used to compute, where they exist, the finite state automata that constitute, for a particular choice of generating set and word-ordering for the object in question, the automatic structure for a group, or a confluent rewriting system of a monoid or group. Approximations to such structures can be calculated where correct structures cannot be found without exceeding time or space constraints. All this is usually done by running automata, which is by far the most important program in the whole of the MAF package. If automata successfully completes, then the automata it has created can solve the word problem for the group or monoid. From now on, unless another program name is explicitly mentioned, when the name MAF is used, in a phrase along the lines of "MAF can do such and such", you should understand that it will usually be done through automata.
automata contains all the functionality contained in the kbprog, autgroup,gpaxioms, and gpminkb components of KBMAG.
Secondly, MAF can also construct various automata related to a given subgroup of a larger group, and the right cosets of this subgroup in the group. When it suceeds in doing so, one can solve problems such as deciding whether a particular word is a member of the subgroup, or whether two words are in the same coset of the subgroup, and, if the subgroup structure was specified appropriately, a presentation of the subgroup is or can be computed. This is also done using automata, which also contains the functionality of the kbprogcos, autcos, and gpmakesubwa components of KBMAG.
Lastly, MAF contains various programs that make use of these automata, and which perform such tasks as reducing any given word or set of words to normal form, enumerating or counting the set of reduced words, or comparing the languages of two different automata that have the same alphabet. Thus, when automata has been run successfully as described in i. and ii., one can use these programs to find the order of a group or monoid, or one of its subgroups, or the index of a subgroup in another group, or test whether a subgroup is normal.
This part of the package also includes programs that manipulate finite state automata in various ways to generate new automata. For example given two automata that each accept words in the same alphabet, one can compute an automaton that accepts the union or the intersection of the two languages, and such automata can therefore be used to calculate the intersection or union of two subgroups. In fact many of the functions in these programs are also used by automata itself.
MAF goes through several stages to during its computations. However users do not generally need to be concerned with this: automata attempts to construct all the automata known to MAF that can be constructed for the input rewriting system. Separate programs are available for performing some of the steps separately, but this is largely to maintain compatibility with KBMAG, and there is very little reason to use these programs (though they might just be useful to help diagnose a problem if it should turn out automata itself is not working correctly). There also some programs that generate some additional automata, but we shall not mention these just yet.
MAF cannot as yet compute automatic structures for groups that are only asynchronously automatic, nor can it compute automatic structures for Braid Groups. These may be added in future, but the author does not think it is likely to be done any time soon.
Open a command prompt window (shell), and log to the directory where you installed MAF. The bin subdirectory contains all the MAF executable files. The examples subdirectory contains a large number of files, most of which have no suffix. These files are used as input to MAF (or KBMAG), and describe rewriting systems. Each is, roughly speaking, a presentation of a group or a monoid, many of them probably well known to you. A good proportion of these example files come originally from KBMAG, so you may be familiar with some of them already. (Files with suffixes beginning with sub are a different type of file, called a substructure file. They describe subgroups of presentations described in a rewriting system). It is suggested that you now log to the bin directory, so that you can easily run the programs it contains.
Let us look briefly at one of these files: d(2_3_5), which can be found in the examples/both subdirectory. It looks like this:
#Von Dyck (2,3,5) group - isomorphic to Alt(5) _RWS := rec ( isRWS := true, ordering := "shortlex", generatorOrder := [a,b,B], inverses := [a,B,b], equations := [ [b^3,IdWord], [(a*b)^5,IdWord] ] );
In a mathematical text this group would probably be presented something like this:
It is hoped that you can see the resemblance, perhaps the main point of difference being the appearance of a third generator B. This is typical of MAF, and of KBMAG: the presentations it works with are not really group presentations, but monoid presentations of groups, so MAF needs to be told that generators are invertible, (when indeed they are) and also needs for the inverses to be named. It would have been possible to name B b^-1 instead, but once you are used to it the convention of using lower and upper case letters for generators and their inverses seems very natural, and is perhaps easier to use on a computer.
We won't worry about the rest of the file for the moment, but will process it with MAF. Assuming you are logged into the bin directory, the following command should do just that:
automata ../examples/both/d(2_3_5)
or if you are running on a Unix like operating system, and don't have . in your path:
This should produce some output on your screen that looks more or less like this:
Looking for new equations using Knuth Bendix process All possible primary equations have been deduced Building Word acceptor from confluent RWS Accepted language contains 60 words. Word acceptor has 29 states Building multiplier Multiplier passes checks Building L1 acceptor The L1 language contains 17 words The L1 acceptor has 37 states. Building reducer The correct difference machine has 34 states. Building primary equation recogniser Primary equation recogniser has 52 states. Correct primary difference machine has 28 states. Building equation recogniser There are 25 equations in the fast rewriting system The equation recogniser has 68 states. Elapsed time 0
Assuming it did, you have successfully run MAF's automata for the first time, and it has created a fair number of finite state automata that can be used for various purposes. You may notice that the ouput contains the line:
Accepted language contains 60 words. Word acceptor has 29 states
The "60" should give you some confidence that automata has indeed analysed this presentation correctly. If you have any doubts you may like to refer to the file d(2_3_5).kbprog which will have appeared in the examples/both directory. This contains the correct minimal reduction system for the group. By the way, KBMAG would say that the word acceptor for this group has 28 states. Internally MAF always counts one more state that appears in output files, because it counts the 0 failure state that is present in every automaton.
If you like you can verify this, by entering commands such as the following a few times:
reduce ../examples/both/d(2_3_5) b*b*a*b
This will print out the correct reduced word for any word you care to give it. (If you abuse MAF by entering invalid words it will complain). MAF always needs to have the * operator between generators, (actually it will accept a word where the generators are separated by spaces as well) . Internally this is not necessarily the case, but most programs in the MAF package use the GAP syntax for expressions. It is possible to get MAF to use a syntax without any separators betweeb generators, but only if you are using its C++ programming API, rather than the ready-built utilities it comes with.
All MAF programs, apart from one or two examples illustrating how MAF can be used as part of another program, are traditional "command line" driven utilities, and do not have a GUI to make them easier to use. Every MAF utility will print out a brief description of itself, and how it should be used, if it is started without any command line arguments. A typical MAF utility will read read at least one text based input file, perform some computation on it, and then generate some other file, which may well in turn be used as input to some other program.
Most MAF utilities accept a good number of "command line options", though it is the author's intention that you should not actually have to use many of these most of the time. In general, options can be specified anywhere on the command line, and in any order, though it is usually a good idea to put all such options before any filenames. Command line options always begin with a '-' character, and must always be separated: you cannot combine several single letter options into one longer option, as is possible with some packages. There are few single letter or abbreviated command line options, and most of these are only included for compatibility with KBMAG. Most command line options in MAF are ordinary English words and phrases, intended to describe the purpose or effect of the option. A few command line options require a parameter, often a number. This must always be specified immediately after the option itself but separated from it by at least one space. For the major components of MAF, such as automata itself, the most useful command line options will be introduced at relevant points in the documentation. A complete summary of all the command line options for all the executables can be found in MAF - Usage information.
All the files written and read by MAF generally conform to the format used by KBMAG. They are cosmetically different, since MAF's output reflects the author's very different preferences for file layout from those used in KBMAG. KBMAG and MAF can each read files produced by the other package. (There are some differences in the file format for coset systems, but MAF can read KBMAG's files, and can produce files in the format it expects.)
Three types of input file are handled:
The programs of MAF produce new files containing rewriting systems or automata.
An example of a rewriting system file was already shown above. The syntax to be used when creating these files is described at the start of MAF for Groups and Monoids.
For a description of the format of files defining subgroups, see MAF for Subgroups and Cosets.
All three types of file are stored similarly, and in fact use a format defined by GAP: they are actually GAP records. Each file contains a single GAP record declaration, which defines one object of one of these types.
The exit code, or error level, of all of the programs is 0 if successful. Various error levels are used if the program fails to complete successfully. Error level 1 occurs if there is a usage error, or the input supplied to the program is invalid in some way. In this case the program aborts with an error message sent to stderr, without producing its normal output. One or two of the programs can also exit with status 2, which means that they have been aborted with provisional or incomplete results. This applies notably to automata, and to two programs provided for KBMAG compatibility kbprog and kbprogcos. Exit level 3 means that the program has failed because of an I/O error. This error would normally be caused by a required file's unexpected non existence, or inaccessiblity, or by the program running out of disk space.
The author is not a fan of "bloatware" and does not want MAF to take up more space on your computer than need be. But, for compatibility with KBMAG, many executable files are included that you will most likely never use. You may safely delete any file that you do not intend to run directly, because none of the executables call other executables to do their work. You can of course delete the examples, though it is probably a good idea to keep at least a few of them until you are familiar with the syntax of input files.
The author is not very familiar with GAP, so the contents of this section should be read with some caution. He is currently preparing a new set of GAP modules which will be designed to work well with MAF and will also allow the user to use KBMAG to perform the same tasks (either via the existing KBMAG package, or by setting an option in the new packakge), so that users will be able to use either package to verify results produced by the other. However, it is already possible to access MAF from within GAP by using the existing KBMAG package, as the next two paragraphs explain.
KBMAG is published as a GAP package for Unix only. However it is certainly possible to get it running under GAP 4.4.x on a Windows machine (the author has done this on both Windows 2000 and Windows XP machines). If the binary files in the gap/kbmag/bin/architecture/ directory are replaced with the corresponding files from MAF, then this package continues to work well - at least with all the examples contained in the KBMAG documentation. This is probably the easiest way to use MAF from within GAP. In fact it is probably best initially only to replace autgroup, autcos, kbprog and kbprogcos. In particular he has not tested whether all the FSA utilities common to KBMAG and MAF can be replaced with MAF versions.
A second possibility is to copy the kbmag subdirectory of GAP's pkg directory to maf and again to replace the binary files. In this case you would also need to various .g files to get them to refer to MAF rather than KBMAG. But it is probably best to leave function names unchanged, since there is no GAP documentation for MAF. The author can supply suitably modified files if anyone is interested. If this is done it is possible to use either MAF or KBMAG to investigate groups. However, unless you go to the trouble of changing a large number of function names, it is not possible to have both packages loaded at the same time.
One notable difference between the existing KBMAG package and the package the author is developing is that the new interface will use the same generator labels in the rewriting system and FSAs as you use in GAP, and will use the case change convention for inverses. Therefore the files produced by the new interface would be more easily usable from outside GAP, and you will therefore be able to save them. This will make it easier to do things like changing the order or names of generators, which is currently error-prone.
Other C++ programs, (and possibly even C programs), should be able to re-use the functionality of MAF. The author's original intention was to build a small library that would contain a function that performed a similar task to KBMAG's autgroup, and not to completely re-implement KBMAG. However, as time as gone on he has found it both useful and interesting to expand this library's capabilities, so that now MAF does contain an almost complete re-implementation of KBMAG (and provides some new functionality as well). The executable files in the package are, in terms of their program-specific source code, small stub programs that use this library, and it is possible to use MAF as a library in other programs. Programmers interested in re-using MAF in this way will have to study the source code, as the author does not have the time to document the API, which is in any case liable to evolve further.