Skochko V. The growth of initial invertible automata

The thesis for obtaining the Candidate of Physical and Mathematical Sciences degree on the speciality 01.01.08 – mathematical logic, theory of algorithms and discrete mathematics. – Taras Shevchenko National University of Kyiv, Ministry of Education and Science of Ukraine, Kyiv, 2021. The work is devoted to investigation of initial invertible Mealy automata and their growth functions. For particular classes of such automata, we obtained the exact values for growth functions. We investigate the question of rationality for the growth functions. Abstract automata give a lot of examples of groups with interesting properties. Active investigations of their algebraic aspects had started when R. Grigorchuk provided the first example of group with intermediate growth between polynomial and exponential. This group can be defined with an automaton over binary alphabet with 5 states. The growth functions of both automaton and corresponding automaton group have the same asymptotic. This connection allows to construct groups with different growth types using automata. On the other hand, investigation of growth function for initial automata was not performed significantly. While the growth of initial automata is not connected directly to the growth of corresponding group, it plays an essential role in algorithmic problems in automaton groups such as order problem. In addition, the growth of initial automaton is preserved after conjugation in the group of finite automata. In this work we obtain the exact formulas for the growth function for some automata classes and investigate different properties of automaton iterations. We consider initial invertible automata with two states over binary alphabet. For such automata we found corresponding growth functions. Also, we prove that the growth function has rational generating function if and only if automaton has finite order or it generates lamplighter group. For every automaton one can construct a sequence of simple graphs based on sequence of automaton iterations. We consider such graphs constructed from initial invertible automata with two states over binary alphabet. We compute chromatic number and girth for every such a graph. In particular we show that girth is either equal to 3 or graph is acyclic. Chromatic number for such a graph is always less or equal to 3. Also, we consider imbalance multisets for considered graph. We prove that for any such a graph multiset of imbalances is always graphic.