权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

双同步自动机、Higman-Thompson 群的外自同构群以及平移自同构。

基本信息

批准号：
EP/R032866/1
负责人：
Collin Bleak
金额：
$ 66.79万
依托单位：
University of St Andrews
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2018
资助国家：
英国
起止时间：
2018 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FR032866%2F1
关键词：
Bi synchronizing automata outer automorphism

项目摘要

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.

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