A bug has been fixed in the code used for FSA minimisation. The bug could cause axiom checking for coset systems to fail erroneously, or the code which generates subgroup presentations to fail.
Version 2.1 of MAF has two new utilities. The more important one, gpxlatwa, allows a word-acceptor for one generating set to be translated into a word-acceptor for any other generating set. This is useful if the desired generating set does not give rise to a natural automatic structure, or if the structure is very difficult to compute.
MAF has recently been updated to fix some bugs in the code used to generate subgroup presentations. Previously Version 2.0.4 fixed bugs in the low-index subgroups program gpsublowindex.
There is a missing quote and misplaced ) in the cosets_FSA.html file in the download. This is now corrected on the MAF web site. You can correct your off-line documentation for MAF by downloading the updated version of the page from here: http://maffsa.sourceforge.net/manpages/cosets_FSA.html
I am currently taking a break from development of MAF to work on my fractal program, Spirofractal, which is likely to take me up until the end of the year.
Since that uses MAF it is quite likely that that will give me a few ideas for how to improve MAF’s facilities for integrating with other software, but it is unlikely to result in any major changes.
When I resume development of MAF my first two priorities are to complete the development of a GAP interface for it, and to make it possible to perform coset enumeration using ACE input files.
I’d appreciate receiving feedback from anyone who uses MAF in earnest on how I could improve it, and what facilities could most usefully be added to it.
V2.0.3 has identical executable files to V2.0.2. A few minor typographical errors in the documentation have been corrected and there is a little more information about the status messages MAF produces while it is working.
V2.0.1 of MAF is now available. This features a few minor bug fixes, most notably one that fixes a problem that stopped automata from completing when a finite index subgroup was processed without -detect_finite_index.
The example input files have been cleaned up somewhat.
I have uploaded new source code and binaries for MAF. This version features many new utilities implementing procedures such as coset enumeration and low index subgroup discovery. It also has extensively rewritten documentation and the 64-bit version uses much less memory.
This release is not quite complete as yet. I intend to change the method used to ensure enough overlaps have been considered when a finite index subgroup is detected by automata, and the documentation probably needs some more corrections. However, I hope it will prove reasonably usable.
The GAP interface for MAF has been on hold for months but I hope to return to this in a few weeks time.
I have recently spent quite a long time using MAF to investigate some groups mentioned in the forthcoming paper “One Relator Quotients of the Modular Group”. I intend to create some Web Pages to be added to the MAF documentation to show how I went about this.
Once that is done I will resume development of the GAP interface to MAF. I’m hoping to have that completed by early December.
When building large automatic structures MAF should now work much quicker. I have taken a look at the algorithm used for FSA minimisation and have been able to make some significant improvements.
There are two main ideas:
1) Automata built by MAF have a significant number of states that are identical post trimming. These states are bound to remain merged, so there is no point inserting them into the hash multiple times.
Therefore the minimisation now does several passes that look for states that are identical. After the first pass more states may well have become identical. For the word acceptor and multiplier this process often reduces the number of states that need to be considered by minimisation by a factor of 5 or 10, so that the actual minimisation runs much quicker.
The second idea is to note that when a state category that is being refined during the minimisation has only one member, no significant further changes are possible for it (the number assigned may change in later passes, but that is all). For such states there is no need to examine the transition table and include it in the hash key.
A category also reaches a steady “decided” state if all its transitions are to “decided” states.
These two observations allow us to reduce the amount of key data in the hash. Although the saving is initially small it will become significant in later passes of minimisation, especially in the case where minimisation is not very effective. This will help to improve cache utilisation and reduce page faulting, especially when the FSA being minimised is very large.