Bi-synchronizing automata, outer automorphism groups of Higman-Thompson groups, and automorphisms of the shift.

最近，数学的几个非常不同的部分之间出现了深刻的联系，如动力学（移位的自同构）、群论（Higman-Thompson群）、组合学（德布鲁因图）和自动机理论（同步）。该项目将发展这些联系，并以这种方式推进这些领域的知识。自动机是有边标记的有向图。想象一下，读取一个方向列表（边标签），并根据方向从图的给定顶点开始行走。这样的自动机是同步的，如果有一个通用的方向列表，那么无论从哪里开始，根据方向遍历边缘，都保证到达一个特定的顶点。（例如，这些技术在工厂自动化、生化计算和卫星控制中都很有用。）De Bruijn图是一类自动机，它具有一个更强的性质，即任何足够长度的列表都会使自动机同步，这一性质表征了De Bruijn图的折叠类。换能器是一种既能读又能写的自动机，因此可以用来将无限的方向列表转换成新的方向列表。换能器是非常自然的对象，用于表示康托空间的同胚，例如n^Z:={0,1，…， n-1}^Z，本课题发展了两类自同构的表示，即n个字母上全移位的自同构Aut（n^Z,s）和经典Higman-Thompson群的自同构Aut（V_n）。（注意群Aut（n^Z,s）和V_n都作用于康托尔空间，就像Aut（V_n）的元素一样。）这里令人惊讶的深层联系是，这些自同构群是紧密相关的（如我们最近的论文所示）。在Kitchens关于符号动力学的经典文本中，我们观察到，Aut（n^Z,s）理论的发展由于缺乏对这一群体元素的有用组合描述而受到阻碍。举个例子，我们甚至不知道群Aut（2^Z,s）和Aut（3^Z,s）是否同构。由于我们现在对这些元素有了新的描述，我们希望推动我们对群Aut（n^Z,s）的理解，特别是解决这个同构问题。Aut（n^Z,s）组的任何进展都将在几个领域产生重大影响。以类似的方式，我们希望接近Higman-Thompson群F_n和T_n （V_n的亲戚）的自同构，正如Brin和Gúzman所分析的那样。这些群具有“外来的”自同构，它们不是很好地理解，但似乎是由换能器携带的。我们希望将我们的技术应用于Brin和Gúzman的论文中列出的一些开放问题。由于折叠的德布鲁因图代表了具有最强同步特性的自动机，我们希望加深对这类自动机的理解将导致对更广泛但重要的同步自动机的理解取得进展。请注意，具有两个边缘标签的随机n顶点自动机以高概率同步（由Berlinkov的工作），我们希望了解自动机的行为中是否存在具有增强同步特性的自然相变。

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.