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

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:

- If a group is generated by two generators, one of which is an involution, the involution should come second.
- If a group is generated by two generators
*a,b*and*a,b,a*b*are all torsion elements make which ever of*a,b,*and*a*b*has the highest order into the first generator, and if possible make the second generator an involution. - If a two generator group can be generated by 3 or 4 involutions, try that as a generating set.

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