Much of the material in this section is taken from a paper by Sarah Rees, with some slight changes to notation.
Let G denote a finitely presented group defined by the presentation G = ⟨ X | R ⟩ where X = {g1, g2,..., gm} and R = {x1=y1,...,xk=yk}. The term generator of G will mean any element of the alphabet X ∪ X-1. lG(w) will denote inf l(u) where u =G w. For any integer i, w(i) will denote the prefix of w of length i if i < l(w), and will otherwise denote the whole of w. We shall use the symbol $ to denote the word of length 0, and e to denote the identity element of the group G (which $ represents).
| (i) | There is a finite state automaton W with alphabet X ∪ X-1 whose language L(W) contains at least one representative of each element of G. |
| (ii) | There is a constant K such that, if v,w ∈ L(W), and lG(v-1*w) ≤ 1, then, ∀i, lG(v(i)-1*w(i)) ≤ K. |
Condition (ii) is often called the fellow traveller property. It can be replaced in the definition above (and often is) by the following condition:
| (ii)* | For each element g of the set {e,g1,..., gm,g1-1,..., gm-1}, there is a 2-variable finite state automaton Mg, with base alphabet X ∪ X-1 whose language is the set of pairs of words (v,w) from L(W) such that v*g =G w. |
W is called the word-acceptor, and Mg the multiplier for g. The word-acceptor and multipliers together form an automatic structure for the group G, and L(W), the associated language. Using the multipliers, any word can be reduced to a representative in the language. In fact, rather than using a separate automaton for each multiplier, it is usual to create an automaton called the general multiplier that encapsulates all the information from the multipliers for a single generator.
The above definition of automaticity appears to be dependent on the choice of generators for G. In fact it is not (see [ECH+92]). It is straightforward to deduce that G is finitely presented.
For the purposes of computational verification of an automatic structure, (ii)* is sometimes more appropriate than the more geometrical condition (ii).
Many of the languages associated with automatic structures are naturally associated with an easily described word ordering. Let ≤ be a partial ordering of words in X. A group G is said to be automatic with respect to ≤ if there is an automatic structure for G for which the language is the set of all irreducible words with respect to ≤.
Let G be a finitely presented group, defined as before, and let H be a subgroup of G. If w is a word on X, then the right coset of w, H*w, is set the set {h*w : h ∈ H}. The notation H*u = H*v denotes that the cosets H*u and H*v are equal as sets. If a word u ∈ H*w then u is is called a representative of H*w. Then G has an automatic coset structure with respect to H if:
| (i) | There is a finite state automaton W with alphabet X ∪ X-1 whose language L(W) contains at least one representative of each right coset of H. |
| (ii)* | For each element g of the set e,g1,..., gm,g1-1,..., gm-1}, there is a 2-variable finite state automaton Mg, with base alphabet X ∪ X-1 whose language is the set of pairs of words (v,w) from L(W) such that H*v*g = H*w. |
The concept of automaticity has not here been defined for general monoids. Automaticity was originally defined only for a group. The concept was extended to embrace coset systems in KBMAG, based on work by Ian Redfern. If we try to define an analogous concept for monoids or semigroups we can see immediately that condition (ii) above will need to be modified, since in general elements of monoids are not invertible. However, condition (ii)* works since it makes no mention of inverses (at least, not if we just specify that X should generate G as a monoid). So the concept of automaticity can be extended to monoids and semigroups and a number of results about such structures are known. However, the author does not know of any procedure for actually constructing automatic structures for monoids, or for verifying that they are correct. The author would be interested to learn of any practical method for the construction of automatic structures for monoids. The methods used to construct automatic structures for groups and coset systems depend on the existence of inverses for all the group generators, and so MAF can only construct automatic structures for groups and their coset systems, not for monoids.