Definitions and Terminology

Let G denote a finitely presented group defined by the presentation:
G = <g₁,g₂,...,g_m | x₁=y₁,...,x_k=y_k>
We shall use the term generator of G to mean any element of the set {g₁, g₂,...,g_m,g₁^-1, g₂^-1,...,g_m^-1}, and word in the generators of G to mean any string of symbols from this set. For words w1,w2 in the generators of G, w1 == w2 will mean that w1 and w2 are identical as strings, while w1 =_G w2 will mean that w1 and w2 represent the same group element of G. Futher, l(w) will denote the string length of w (for example, l(g₁⁵g^-3₂) = 8) and l_G(w) the string length of a shortest word u with u=_Gw. 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).

A finite state automaton M is a finite directed graph, whose edges are labelled by symbols from an associated set known as its alphabet, and whose vertices are called states. Out of each state there is at most one edge labelled with any given alphabet symbol. One vertex (or state) is known as the start state, some of the others are accept states. A string on the alphabet is accepted (and so is in the language, L(M), of M) if it labels a path from the start state to an accept state, and is otherwise rejected. Since transitions out of some states on some symbols may be undefined, an automaton satisfying these conditions is often known as a partial deterministic automaton. A set of words is called a regular set if it is the language of a finite state automaton.

A 2-stringed automaton is a finite state automaton whose alphabet is a set of ordered pairs of symbols from a base alphabet. The language can be considered as a set of pairs of words over the base alphabet; pairs of words are read by the automaton by reading at each stage a pair of symbols, one from each string. If one word is longer than the other, then the shorter word is padded out with a padding symbol, which we shall denote by _, until the two words are equal in length.

Definition 2.1 (Automatic group) G is automatic if:

1. There is a finite state automaton W with alphabet {g₁,...,g_m,g₁^-1,...,g_m^-1} whose language L(W) contains at least one representative of each element of G.
2. There is a constant K such that, if v,w 2 L(W), and l_G(v^-1*w) ≤ 1, then, for all i, l_G(v(i)^-1*w(i)) ≤ K.

Condition (ii) is known as the fellow traveller property. It can be replaced in the definition (and often is) by the following condition:-
(ii)* for each element g of the set {e,g₁^-1,...,g_m^-1}, there is a 2-stringed finite state automaton Mg, with base alphabet {g1,..., gm, g₁^-1,...,g_m^-1} whose language is the set of pairs of words (v,w) from L(W) such that v*g=w.

For the purposes of computational verification of an automatic structure, (ii)* is sometimes more appropriate than the more geometrical condition (ii). 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.

The above definition of automaticity appears to be dependent on the choice of generators for G. In fact it is not (see Word processing in proups (Epstein et al.) ). It is straightforward to deduce that G is finitely presented.

Many of the languages associated with automatic structures are naturally associated with an easily described word order.

Definition 2.2 (Automatic with respect to a word order) Let ≤ be any partial order on words. A word v is said to be irreducible with respect to ≤ if there is no word u with u =_G v and u ≤ v (that is with u =_G v and u < v).

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