In this tutorial you will learn that the choice of generating set, and the order in which the generators are specified can strongly influence the size of the automata MAF creates. It can even influence which automata MAF is able to create. You will also learn that your mathematical training may well lead you into making poor choices. This matters because the larger an automaton to be computed by automata is, the more difficult it is likely to be to find.
The tutorial uses four different input files for a very well known and important group: the group of rotational symmetries of the tessellation of (2,3,7) hyperbolic triangles, often known simply by some notation such as 2 3 7, and a member of the Von Dyck family of groups. There are many other input file for groups like this included in the examples directories. The author has named most of these D(p_q_r) where p,q,r are the three numbers representing the angles of the triangle which is (half of) the fundamental region of the tessellation. There are also input files T(p_q_r) which are for the corresponding triangle groups: that is the group of reflectional symmetries of the tessellation, and which contain the Von Dyck group as a subgroup of index 2. However, in this lesson, for ease of typing we shall use a simpler scheme.
Open a command prompt window (shell), and make the examples subdirectory the current directory. The lesson2 subdirectory of this directory contains four input files for the group 2,3,7. These files and the corresponding presentations are as follows.
| filename | Presentation |
|---|---|
| 237 | <a,b | a^2=b^3=(a*b)^7=1> |
| 327 | <a,b | a^3=b^2=(a*b)^7=1> |
| 723 | <a,b | a^7=b^2=(a*b)^3=1> |
| 723_abc | <a,b | a^7=b^2=c^3=a*b*c=1> |
You are invited to run automata against each of these input files. There is no need to use any special options: all the runs will complete very quickly. Most mathematicians, if invited to give a presentation for this group, would surely choose the first.
Take a look at the output files created for each with your directory listing program. You should see that the files for 237 and 327 are almost the same size, with the 327 files a little smaller on average, but the files for 723 and 723_abc are distinctly smaller. The files for 723_abc are larger than for 723, but considering the fact that there is an extra generator, smaller than one might expect. Much more importantly, 723_abc has a confluent rewriting system. This means that we can expect word reduction to be faster for this presentation than for the others when dealing with long words.
Since file sizes are not a very mathematical metric let us take a look at the number of states in some of the automata.
| filename | Primary Word differences | Word-acceptor | Multiplier |
|---|---|---|---|
| 237 | 30 | 52 | 135 |
| 327 | 28 | 50 | 133 |
| 723 | 14 | 29 | 84 |
| 723_abc | 13 | 25 | 72 |
The user is encouraged to try other orderings of the generators or other generating sets. For example, groups generated by generators a,b of order 2 and 3 are also generated by a*b and a*b^-1, and hence also by a*b and a*b*a*b^-1. Those generating sets work well with coset enumerators, but the author has found they work less well with MAF - where it seems "geometric" generators often work best.
It is not possible to give hard and fast guide-lines, but this behaviour does seem fairly typical, and some good rules of thumb seem to be:
It is interesting to see how far the smaller size of the automata for the last two generating sets carries across to quotient groups. The lesson2 subdirectory also contains analogous input files for the two sets of quotients of 2,3,7 in which the commutator has order 8 and order 12. The former is a moderately large finite group, the latter infinite.
When running automata against these two sets of input files the user is advised to use the -confluent command line option against the set of files for the commutator of order 8, and to use the -nokb command line option against the set of files for the commutator of order 12. The latter is especially important. The computation of the automata for the second set of groups is a reasonably substantial one.
You will encounter mixed results - for the commutator of order 8 quotient all the computations take roughly the same length of time, though 7238_abc is marginally slower than the rest. There does not seem to be any major differences in the sizes of the automata for the different presentations, at least, there is no clear winner for this set of presentations. Things are very different with the second set however: on the author's machine the computations for 72312_abc and 72312 are substantially faster than the computations for 23712: with the first two taking 31 and 42 seconds respectively, and the latter requiring 210 seconds. The automatic structure for 72312_abc is less than half the size of that for 23712.