MAF : Tutorials : 1 - Processing an input file with automata

MAF Tutorial 1 : Processing an input file with automata

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, but the MAF documentation will generally refer to them simply as input files. 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. 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.

Let us look briefly at one of these input 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 they work with are not really group presentations, but monoid presentations of groups. 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.

We shall not concern ourselves with the format of this file for the moment (you can find out more in Input files), but will process it with MAF. It is suggested that you now log to the bin directory, so that you can easily run the programs it contains. Assuming you have done so, 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 output 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 for FSA than appears in output files, because it counts the 0 failure state that is present in every automaton.

If you like you can multiply group elements together 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 input word you care to give it. MAF always needs to have the * operator between generators. (It is possible to get MAF to use a syntax without any separators between generators, but only if you are using its C++ API, rather than the ready-built utilities it comes with).

You can also find out the order of any group element with a command such as the following:

gporder ../examples/both/d(2_3_5) a*b*a*B