Recently, deep connections have arisen between several very different parts of mathematics such as dynamics (automorphisms of the shift), group theory (Higman-Thompson groups), combinatorics (de Bruijn graphs), and automata theory (synchronization). The project will develop these connections and in this way advance knowledge of these fields.
An automaton is an edge-labelled directed graph. One imagines reading a list of directions (edge-labels), and walking from a given vertex of the graph according to the directions. Such an automaton is synchronizing if there is a universal list of directions so that wherever one starts, upon traversing edges according to the directions, one is guaranteed to reach a specific vertex. (These are useful in automation in factories, in biochemical computing, and in control of satellites, for instance.) De Bruijn graphs are a class of automata with the stronger property that any list of sufficient length will synchronize the automaton, and this property characterises the class of foldings of de Bruijn graphs. A transducer is an automaton which writes as well as reads, and so can be used to transform infinite lists of directions into new ones. Transducers are extremely natural objects for representing homeomorphisms of Cantor spaces such as n^Z := {0,1, ..., n-1}^Z, and this project develops these representations for two classes of automorphisms, Aut(n^Z,s), the automorphisms of the full shift on n letters, and Aut(V_n), the automorphisms of the classical Higman-Thompson groups. (Note that the groups Aut(n^Z,s) and V_n both act on Cantor spaces, as do the elements of Aut(V_n).) The surprising and deep connection here is that these groups of automorphisms are strongly related (as shown in our recent paper).
In Kitchens' classical text on symbolic dynamics, it is observed that developing the theory of Aut(n^Z,s) is hampered by a lack of a useful combinatorial description for elements of this group. An example of this is the fact it is not even known if the groups Aut(2^Z,s) and Aut(3^Z,s) are isomorphic. As we now have a new description of these elements, we hope to push forward our understanding of the group Aut(n^Z,s), and in particular to resolve this isomorphism question. Any progress on the group Aut(n^Z,s) will have significant impact in several fields.
In similar fashion, we hope to approach the automorphisms of the Higman-Thompson groups F_n and T_n (relatives of V_n) as analysed by Brin and Gúzman. These groups have `exotic' automorphisms, which are not very well understood, but which appear to be carried by transducers. We would like to apply our technology to some of the open problems listed in the paper of Brin and Gúzman.
As folded de Bruijn graphs represent the automata with the strongest possible synchronizing property, we hope that developing our understanding of this class will lead to progress in understanding the broader, but important, class of synchronising automata. Note that a random n-vertex automaton with two edge labels is synchronizing with high probability (by work of Berlinkov) and we hope to understand if there is a natural phase transition in the behaviour of automata with increasing strong synchronization properties.
|