Asymptotic, Algorithmic and Geometric Aspects of Groups Generated by Automata

摘要

This dissertation is devoted to various aspects of groups generated by automata. Westudy particular classes and examples of such groups from different points of view. Itconsists of four main parts.In the first part we study Sushchansky p-groups introduced in 1979 bySushchansky in "Periodic permutation p-groups and the unrestricted Burnsideproblem". These groups represent one of the earliest examples of Burnside groupsand, at the same time, show the potential of the class of groups generated by automatato contain groups with extraordinary properties. The original definition is translatedinto the language of automata. The original actions of Sushchansky groups on p-ary tree are not level-transitive and we describe their orbit trees. This allows usto simplify the definition and prove that these groups admit faithful level-transitiveactions on the same tree. Certain branch structures in their self-similar closuresare established. We provide the connection with so-called G groups introduced byBartholdi, Grigorchuk and Suninc in "Branch groups" that shows that all Sushchanskygroups have intermediate growth and allows us to obtain an upper bound on theirperiod growth functions.The second part is devoted to the opposite question of realization of knowngroups as groups generated by automata. We construct a family of automata with n states, n greater than or equal to 4, acting on a rooted binary tree and generating the free products ofcyclic groups of order 2.The iterated monodromy group IMG(z2+i) of the self-map of the complex plainz -> z2 + i is the central object of the third part of dissertation. This group actsfaithfully on the binary rooted tree and is generated by 4-state automaton. We providea self-similar measure for this group giving alternative proof of its amenability. Wealso compute an L-presentation for IMG(z2+i) and provide calculations related to thespectrum of the Markov operator on the Schreier graph of the action of IMG(z2 + i)on the orbit of a point on the boundary of the binary rooted tree.Finally, the last part is discussing the package AutomGrp for GAP system developedjointly by the author and Yevgen Muntyan. This is a very useful tool for studyingthe groups generated by automata from the computational point of view. Mainfunctionality and applications are provided.