MAF : Appendices : (A) MAF and KBMAG compared

Appendix A : MAF and KBMAG compared


Additional Facilities

  1. Groups and monoids

    For computations with groups and monoids MAF includes several new utilities which can:

  2. Coset systems

    For computations with coset systems MAF can:

    All these facilities, together with the new program simplify, make coset systems a much more useful feature than they were in KBMAG. These extra facilities require you to use MAF directly, because the GAP components of KBMAG would be confused otherwise.

  3. Non-shortlex automatic structures

    MAF can, in principle, compute automatic structures using any supported word-ordering, not just "shortlex" automatic structures. However, such computations are often significantly more difficult than for "shortlex". Such structures often do not exist, even when the rewriting system is confluent. In fact, the author has not been able to find any group which has an automatic structure that can be computed using MAF, but which does not have either a "shortlex" automatic structure (possibly using another set of generators) or else a confluent rewriting system for the choice of generators and ordering in question. So this new facility appears to be of limited use. The author would be very interested to learn of any groups for which it is genuinely useful. Success is very likely with word-orderings that can be recognised by a finite state automaton, or for orderings (such as "wtlex") that can be recognised by an automaton which only needs to keep a very small amount of information about words. Success is much less likely with wreath-product type word-orderings, and even less likely where these assign different levels to a generator and its inverse.

Performance with difficult input files

When MAF or KBMAG are asked to perform computations using very difficult presentations it is impossible to know in advance which will succeed faster, or indeed whether either will succeed at all. Though the author hopes that MAF will usually out-perform KBMAG by a wide margin this is by no means always the case. It is always possible that the groups you are interested in might be better suited to KBMAG than to MAF.

Migrating to MAF

For computation with input files representing groups or monoids, automata contains all the functionality contained in the kbprog, autgroup, gpaxioms, and gpminkb components of KBMAG.

Computation with input files representing subgroups is also performed using automata, which also contains the functionality of the makecosfile, kbprogcos, autcos, and gpmakesubwa components of KBMAG.

You can continue to invoke all the KBMAG programs separately rather than using automata if you wish but you may like to note that in MAF, kbprog, gpmakefsa, autgroup, kbprogcos, autcos, are all almost identical to MAF's automata.

FSA programs included in KBMAG missing from MAF

  1. nfadeterminize MAF cannot yet process non-deterministic automata at all. There is no reason for it to do so, since they are not needed. The forthcoming GAP package for MAF will support non-deterministic automata, but will, in the first instance, use KBMAG's nfadeterminize program to determinise them.
  2. fsagrowth In KBMAG these compute rational functions that describe the size of the language at various word lengths. The present author has not been at all interested in this functionality as yet. You can of course use the KBMAG fsagrowth with automata produced by MAF.
  3. fsafilter Replaced in MAF by fsaprint for reasons described in the documentation.
  4. fsalabmin MAF's fsamin works with labelled FSA.