Input files

We describe here the format used by MAF and KBMAG for a file representing a rewriting system. Files in this format are the primary means of supplying input to MAF. MAF will also often generate files in this same format as part of its output. To distinguish between the two uses of this file format, the documentation will refer to a rewriting system used as input as an input file. A more formal, though still incomplete, definition of the syntax of these files than is given here can be found in the GASP Standard Format Document.

The example below is a typical example of an input file

#Free nilpotent group of rank 2 and class 2
_RWS := rec
(
  isRWS := true,
  generatorOrder := [c,C,b,B,a,A],
  ordering := "recursive",
  inverses := [C,c,B,b,A,a],
  equations := 
  [
    [b*a,a*b*c],
    [c*a,a*c],
    [c*b,b*c]
  ]
);

Comments

The first line is a comment, and is ignored by programs. Comments are preceded by the # symbol and last to the end of the line, and can appear anywhere in an input file. It is a good idea to add such comments to input files, especially if you are investigating a number of similar presentations, or investigating quotients of a group whose structure you don't know yet. When creating a new input file from an old one you should also remember to remove any comments that no longer apply! Comments are also useful if you are trying to find out whether the relations given as axioms for a presentation are all necessary: one "comments out" one or more relations, and then runs automata against the modified input file to see if MAF can still compute the same automata.

GAP record syntax

All MAF's input and output files are formatted as GAP records, (though GAP cannot actually parse the files directly). Line 2 of the input file, _RWS := rec, begins the definition of a GAP record, with the name of record being defined appearing on the left. To comply with the KBMAG GAP interface, we name our rewriting system _RWS. A record definition consists of a number of comma-separated field definitions, which are enclosed by matching opening and closing parentheses (,), and which describe the record in detail. In the present case the first field definition states that this is a definition of a rewriting system. This line must always be present. Note the use of := rather than = in field definitions, and remember that each field within the object is separated from the next by a comma (but there is no comma after the last field definition). It is easy to forget these points, and neither MAF nor KBMAG are at all forgiving of syntax errors.

GAP lists

You will notice the use of square brackets [] in several places. Such brackets always enclose a list of similar items, possibly another list, as in the case of the equations field. A list can have gaps, which is indicated by there being no text other than spaces between two or more adjacent commas. A list can also be empty, which is indicated by there being nothing at all between the opening [ and the closing ]. Much of the most important information in an input file is contained in such lists.

generatorOrder

First comes a list of generators. These must generate the structure as a monoid, even if it is a group; this means inverses should be included in the generator list. The field is named generatorOrder to emphasize the fact that the order is relevant - it will affect the ordering of words in the alphabet, and hence which words are "reduced".

Generator names

The names of the generators that appear in the generatorOrder list should be alphanumeric strings, though they can also contain underscores ('_') and periods('.'). A generator name must begin with either an alphabetic character or an underscore, not a digit or period. Case is significant. It is recommended that, whenever possible, you use single letters, and use case-change for inversion, as in this example. Another policy is to use a common prefix followed by numbers; for example, a file output by GAP might have its generators named G.1, G.2, ..., G.n for some n ≥ 0. It is also permissible to name a generator name^-1, where name is the name of another generator, and the two are mutually inverse. Any other use of ^-1, or of the ^ and - characters, in a name is forbidden.

ordering

The ordering field specifies which ordering on words in the input alphabet is to be used. Although there is a default word-ordering, which is "shortlex", this field is required by the KBMAG GAP interface, so it is recommended that it should always be included, although most of the time you probably will want to use "shortlex" ordering. The word-ordering options are discussed in detail in Word-ordering methods. Note that the double quotes are required around the value given for this field. The ordering field must come before the list of equations.

inverses

The inverses field supplies the list of two-sided inverses of the generators, in the same order as the generators. This field must be present, but, in general, not all generators need have inverses, so the list could be empty, or contain gaps. For example, if only the first and third generators have inverses, and these are named i1 and i2, then the list would be written as [i1,,i2]. However, if generator A is listed as the inverse of a, then a must also be listed as the inverse of A (any mistakes here will result in generators you intended to be distinct elements being equal). One sided inverses must not be specified here, but can be specified using equations. Note that you need to change the order of the inverses if you change the order of the generators.

equations

Finally, there comes the equations field. This consists of a list of lists. Each inner list constitutes a defining relation for the monoid, and should have two entries, which are words in the generators, and are the left and right hand sides of a relation. If there are no defining relations then you must specify an empty list - MAF will not allow this field to be omitted altogether. The syntax to be used for words is explained below. It is not necessary, but not harmful, to include defining relations of type [a*A,IdWord] in the list of equations, where the generators a and A have been already been specified as mutually inverse in the inverses field. (If you do do this then MAF will issue a diagnostic noting that an axiom is redundant). In MAF, you do not need to worry about which of two terms should be on the left. Nor do you need to worry about "balancing" the equation (which means replacing a generator on the left or right by its inverse on the other side of the equation, usually with the aim of equalising so far as possible the number of generators on each side). In KBMAG this might make a difference, at least in the case of a recursive ordering being used, but it is unlikely to do so in MAF.

Syntax for words

The empty word is denoted by IdWord. IdWord must stand alone - it may not appear as part of an expression. Words may contain parentheses to any level, and positive powers. So, for example a*(b*(A*c)^4)^3*c^12 is a valid word in the generators in the example above. Negative powers are permitted on generators for which an inverse has been specified. MAF also permits negative powers on expressions involving only invertible generators, but KBMAG does not. Neither KBMAG nor MAF accept a^b as an abbreviation for b^-1*a*b.

Optional fields

There are a number of other optional fields, which do not occur in this example. The most important of these are provide additional information required for some word-orderings and are discussed in Word-ordering methods. Some other optional fields provide further detailed instructions for automata or more particularly KBMAG's kbprog. Such optional fields are listed in the usage information for kbprog.