Growth of initial invertible automata with two states over binary alphabet
Рік:
2017
Сторінок:
Р. 9-14
Тип документу:
Стаття
Головний документ:
Київський Вісник Київського національного університету імені Тараса Шевченка / Київський, університет імені національний; редкол.: голов. ред. Анісімов А.В. ; Хусаінов Д.Я., Arturs Medvids, Miklos Ronto [та ін.]. - Київ, 2017
Анотація:
Automata were introduced in the middle of the 20th century to investigate the properties of di erent computational schemes. They appeared as a part of applied mathematics but now automata are widely used in such abstract areas as group theory and dynamical systems. In particular, automata were used to solve the Milnor problem on group growth.
An initial automaton is a model which allows us to realize certain transformations of a set of words over some nite alphabet. The growth function of such an automaton counts the minimal number of states in the automata that implement di erent powers of corresponding action on the given set of words. In this article we consider the initial invertible automata with two states that act on the set of binary words. We compute the growth function for each automaton from this automata class. As a corollary we prove that the only in nite order automata in this class with rational (algebraic) growth function are the lamplighter automata.
