Cayley graphs and automatic sequences

详细信息    查看全文

• 作者：Pierre Guillot
• 关键词：Automatic sequences ; Automata ; Cayley graphs ; Dessins
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：45
• 期：1
• 页码：245-270
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Order, Lattices, Ordered Algebraic Structures; Computer Science, general; Group Theory and Generalizations;
• 出版者：Springer US
• ISSN：1572-9192
• 卷排序：45

文摘

We study those automatic sequences which are produced by an automaton whose underlying graph is the Cayley graph of a finite group. For 2-automatic sequences, we find a characterization in terms of what we call homogeneity, and among homogeneous sequences, we single out those enjoying what we call self-similarity. It turns out that 2-self-similar sequences (viewed up to a permutation of their alphabet) are in bijection with many interesting objects, for example dessins d’enfants (covers of the Riemann sphere with three points removed). For any p, we show that, in the case of an automatic sequence produced “by a Cayley graph,” the group and indeed the automaton can be recovered canonically from the sequence. Further, we show that a rational fraction may be associated with any automatic sequence. To compute this fraction explicitly, knowledge of a certain graph is required. We prove that for the sequences studied in the first part, the graph is simply the Cayley graph that we start from, and so calculations are possible. We give applications to the study of the frequencies of letters.