Introduction

Advice to Reader

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.

What is MAF?

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.

Comparison with 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 .

Overview

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.

  1. 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.

  2. 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.

  3. 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.

A First Example of the Using MAF

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:

gp <a,b | a2=b3=(ab)5=1>

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:

./automata ../examples/both/d(2_3_5)
(Sadly that command line does not work on Windows machines unless you are using a Unix like shell)

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.

User Interface

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.

File Formats

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:

  1. The Rewriting System input files used by automata and related applications.
  2. For applications related to cosets of subgroups, an additional input file defining generators of the subgroup must also be supplied by the user.
  3. Files containing the finite state automata produced by these programs, which are used by input by some of the other programs.

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.

Exit Code of Programs

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.

Pruning MAF

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.

Using MAF from within GAP

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.

Reusing MAF Source Code

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.