13 - Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms  pp. 375-404

Automorphisms of the binary tree: state-closed subgroups and dynamics of 1/2-endomorphisms

By V. Nekrashevych and S. Sidki

Image View Previous Chapter Next Chapter



Introduction

Automorphisms of regular 1-rooted trees of finite valency have been the subject of vigorous investigations in recent years as a source of remarkable groups which reflect the recursiveness of these trees (see [S1], [G2]). It is not surprising that the recursiveness could be interpreted in terms of automata. Indeed, the automorphisms of the tree have a natural interpretation as input-output automata where the states, finite or infinite in number, are themselves automorphisms of the tree. On the other hand input-output automata having the same input and output alphabets can be seen as endomorphisms of a 1-rooted tree indexed by finite sequences from this alphabet. It is to be noted that the set of automorphisms having a finite number of states and thus corresponding to finite automata, form an enumerable group called the group of finite-state automorphisms. The calculation of the product of two automorphisms of the tree involve calculating products between their states which are not necessarily elements of the group generated by the two automorphisms. In order to remain within the same domain of calculation we have defined a group G as state-closed provided the states of its elements are also elements of G [S2]. Among the outstanding examples of state-closed groups are the classes of self-reproducing (fractal-like) groups constructed in [G1, GS, BSV] which are actually generated by automorphisms with finite number of states, or equivalently, generated by finite automata.