MAF : Background : The general multiplier and word-differences

The general multiplier and word-differences

The general multiplier automaton

If an automatic structure exists for a group or coset system, all the information contained in the word-acceptor and the various multipliers can be stored in a single FSA. This FSA is called the general multiplier, and it has labelled accept states. If the word pair (u,v) is accepted then u and v are both accepted words (accepted by the word-acceptor that is), and the label for the accept state consists of a list of words. Each word in the list of words forming the label is either IdWord or a word consisting of one of the generating symbols from the alphabet. A word w is on the list when it is true that u*w =G v, (or, in the case of a coset system that H*uw = H*v. In the usual case where none of the generators is itself reducible to one of the other generators, each label will contain exactly one word: either IdWord or one of the generators. In fact, it is not hard to see that we can extend this concept further, and include any word in the label for a word pair (u,v) that makes uw=v a true equation. However, it is only useful to do so if we have a complete solution to uw=v for every uL(W). To do this for words other than the empty word and the generators, we generally would need more states in the FSA, and the number of states would increase as we increase the number of multipliers we support. If we start from the general multiplier an algorithm exists for producing the multiplier for any finite set of elements from the group.

The finite set of word-differences of an automatic structure

The existence of a word-acceptor and multipliers gives us some important information about a group, which we have already hinted at in the discussion of the general multiplier FSA. Let us consider what it means if, in the process of testing two distinct word pairs (u,v), and (t,w) for acceptance by a general multiplier, both pass through some state σ. So, we have found that we can reach state σ by two distinct routes (u0*u1*...*un,v0*v1*...*vn) and (t0*t1*...*tm,w0*w1*...*wm). But, assuming we have constructed the a "trim" FSA, we can now find two further words, (r0*r1*...*rk,s0*s1*...*sk) such that both (u0*...*un*r0*...*rk,v0*...*vn*s0*...*sk) and (t0*...*tm*r0*...*rk,w0*...*wm*s0*...*sk) are accepted with some label g.

This means that with each state of the FSA we can associate a definite element from the group, because, r0*...*rk*g*Sk*...S0 =G Un*...*U0*v0*...*vn and r0*...*rk*g*Sk*...S0 =G Tn*...*T0*w0*...*wn

So given any equation between words of the form ug = v, we can form the series of elements, 1, U0*v0, U1*U0*v0*v1,Un*...Un*U1*U0*v0*v1*...vn =g, G*g=1. Each such element will be represented by the reduced word for the element. This is a path from and back to the identity element of the group, or from IdWord and back. Each of these elements is called a "word-difference", and we have just shown that if the general multiplier exists there are only finitely many of them. Also, we can use the fact that there are finitely many word-differences in order to construct the word-acceptor and then the general multiplier.

we shall make a few general comments about the properties of the set of word-differences:

  1. The set of word-differences always includes IdWord. This is obvious from the construction.
  2. The set of word-differences always includes each generator g, except in the case where the generator is reducible. This is because our original set of generators is closed under inversion so that for every g, G*g=IdWord is an equation, and the element g arises as a word-difference of this equation.
  3. The set of word-differences is closed under inversion. This is because every word-difference by definition arises from an equation of the form ug =G v is which u and v have no common prefix and both are reduced. If ug =G v is an equation and v is not IdWord, then vG =G u must also be an equation. For vG is certainly equal to u, and vG > u because if vG =G u we could cancel v from the right and left of the equation ug =G v contrarary to our claim that u and v have no common prefix. Finally vG is not less than u because if it were then it would be a reduction of u contrary to u being irreducible. To deal with case of equations of the form ug =G Idword: these must be those of the form Gg =G Idword, and we insisted that our alphabet was itself closed under inversion.