Heuristic Example

The most important question about a finite presentation is whether or not the group it defines is infinite. As is well known, this question is undecidable. Nevertheless coset enumeration is often effective in verifying that a particular presentation defines a finite group or more generally in showing that a finitely generated subgroup is of finite index.

When it succeeds, coset enumeration produces a coset table whose rows correspond to cosets and columns to generators. The table entries record the effect of multiplying a coset by a generator. When coset enumeration fails, it leaves behind a partial coset table which might contain lots of information. Rather than throw this information away, we would like to use it to learn more about the group. The following example shows that concepts from formal language theory apply to this situation in a natural way.

We try to enumerate the cosets of the identity subgroup < 1 > from the presentation G = < a, b | ab = ba >. We are bound to fail as there infinitely many cosets. Suppose we run out of room with the partial coset table
a A b B
1 2 3 4 5
2 - 1 6 7
3 1 - - -
4 6 - - 1
5 7 - 1 -
6 - 4 - 2
7 - 5 2 -

which is equivalent to the directed graph


This graph maps onto a portion of the Cayley diagram of G with vertex C1 going to 1. We can deduce that there is a path in the Cayley diagram from the image of vertex C6 to the image of C2 with label B. Likewise the label of any path in the Cayley diagram from the image of C2 to 1 can be extended to the label of a path from the image of C6 to 1 by adding a B at the beginning.

Record the above observation as the rewrite rule (C6) --> B(C2). Each edge gives us a similar rule, and it is not hard to show that these rules generate the labels of all visible paths. For example the derivation

(C1) --> B(C5) --> Ba(C7) --> Bab(C2) --> BabA(C1)

yields the label of a path from C1 to C1. As we are particularly interested in paths from C1 to itself, we add for each rule ending in C1 a new rule with that occurrence of C1 deleted. Now we have derivations like

(C1) --> B(C5) --> Ba(C7) --> Bab(C2) --> BabA

In other words we have a regular grammar for a sublanguage of W, the language of all words defining the identity in G. With the stipulation that C1 be the start state and terminal state the graph above becomes a finite automaton accepting this sublanguage.

Our regular grammar generates the labels of certain paths from 1 to 1 in the Cayley diagram of G. As we noted above, these are the labels of paths visible in the graph above. However, we can use more powerful grammars to derive the labels of some invisible paths. These grammars are constructed from the graph above and the knowledge that G acts as isomorphisms of its Cayley diagram.

Let us ignore the distinction between the vertices C1 ... C7 and their images in the Cayley diagram. If w is the label of any path (in the Cayley diagram) from C2 to C4, then BwB is the label of a path from C6 to C1. But paths from C2 to C4 have exactly the same labels as paths from C7 to C1. Thus the rewrite rule

(C6) --> B(C7)B

is valid in the sense that replacing the label w of any path from C7 to 1 by BwB yields the label of a path from C6 to 1. We may add this rule and others like it to our collection with confidence. Any word we can derive by rewriting C1 will indeed be the label of a path from 1 to 1 in G.

Our augmented collection of rules forms a linear grammar. In addition to generating a larger part of W than the original regular grammar, linear grammars like the one we have described can serve as a starting point for the Epstein-Holt-Rees procedure to construct an automatic structure for G. A derivation (C1) --> ... --> w(C5)v plays the role of an accepting path for the pair (w,v) in the comparator automaton for the generator b.

There are still more rewriting rules we can add. Consider a path which starts at C2 with first edge labeled a and ends at C1. The first edge of this path leaves the graph above; but the path must return, say to C6, and continue on to C1. The part of this path beginning after the first edge and ending at C6 will have a label which is also the label of a path from C7 to C1. Thus we have the rule

(C2) --> a(C7)(C6).

Adding rules of this type yields a context-free grammar which might generate even more of W than our linear grammar. A result of Muller and Schupp tells us we will not obtain all of W unless G has a free subgroup of finite index; however, we may still hope to use the context-free grammar to our advantage.