9 - Automata groups

Summary

In contrast to the previous chapters, where the languages we dealt with were languages over a symmetric generating set for a group, we will now use automata to define group elements. The basic idea, which dates back at least to Alěshin [3], is that certain mappings from A* to itself can be described by automata with output capabilities, so called Mealy machines.

The real starting point for a systematic study of such groups was the discovery of the first groups of intermediate growth in this class of groups by Grigorchuk [114] and Gupta and Sidki [129]. These groups naturally act on homogeneous rooted trees and many of them reflect the self-similar structure of the tree (see 9.3.13), which often allows for inductive arguments.

The realisation of iterated monodromy groups of partial self-coverings of orbispaces as automata groups by Nekrashevych [201] has given the subject another boost. This strongly links dynamical systems of post-critically finite rational functions and their Julia sets to contracting self-similar automata groups and their limit dynamical systems; see Section 9.3.16. Their study from a more automata theoretic point of view is a more recent development; see Sections 9.4 and 9.6.

Introducing permutational transducers

Finite state transducers A finite state transducer is a finite state automaton with an output function. So besides the input alphabet A there is now also an output alphabet B whose letters will be written to an auxiliary write-only output-tape. Also, each transition must now specify a finite, possibly empty, output string over B that will be written to the output-tape when the transition is made. We shall abbreviate finite state transducer and its plural by fst.

An fst simply translates strings over A into strings over B. As such, it does not accept input words, and so there is no need for accepting states. However, it may sometimes be useful to allow accepting states in order to validate the input and/or output; see 9.1.4.