Spelling suggestions: "subject:"duas automata""
1 |
Asymptotic, Algorithmic and Geometric Aspects of Groups Generated by AutomataSavchuk, Dmytro M. 14 January 2010 (has links)
This dissertation is devoted to various aspects of groups generated by automata. We
study particular classes and examples of such groups from different points of view. It
consists of four main parts.
In the first part we study Sushchansky p-groups introduced in 1979 by
Sushchansky in "Periodic permutation p-groups and the unrestricted Burnside
problem". These groups represent one of the earliest examples of Burnside groups
and, at the same time, show the potential of the class of groups generated by automata
to contain groups with extraordinary properties. The original definition is translated
into 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 us
to simplify the definition and prove that these groups admit faithful level-transitive
actions on the same tree. Certain branch structures in their self-similar closures
are established. We provide the connection with so-called G groups introduced by
Bartholdi, Grigorchuk and Suninc in "Branch groups" that shows that all Sushchansky
groups have intermediate growth and allows us to obtain an upper bound on their
period growth functions.
The second part is devoted to the opposite question of realization of known
groups 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 of
cyclic groups of order 2.
The iterated monodromy group IMG(z2+i) of the self-map of the complex plain
z -> z2 + i is the central object of the third part of dissertation. This group acts
faithfully on the binary rooted tree and is generated by 4-state automaton. We provide
a self-similar measure for this group giving alternative proof of its amenability. We
also compute an L-presentation for IMG(z2+i) and provide calculations related to the
spectrum 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 developed
jointly by the author and Yevgen Muntyan. This is a very useful tool for studying
the groups generated by automata from the computational point of view. Main
functionality and applications are provided.
|
Page generated in 0.0806 seconds