The smallest Mealy automaton of intermediate growth

Abstract

In this paper we study the smallest Mealy automaton of intermediate growth, first considered by the last two authors. We describe the automatic transformation monoid it defines, give a formula for the generating series for its (ball volume) growth function, and give sharp asymptotics for its growth function, namely [ F(n) \sim 2^{5/2} 3^{3/4} π^{-2} n^{1/4} \exp{π\sqrt{n/6}} ] with the ratios of left- to right-hand side tending to 1 as $n\to \infty$.

References in corpus (1)

• Dimension and randomness in groups acting on rooted trees

Cited by in corpus (10)

• Growth of permutational extensions
• Implementing Computations in Automaton (Semi)groups
• On the Finiteness Problem for Automaton (Semi)groups
• Classification of groups generated by 3-state automata over a 2-letter alphabet
• Varieties
• The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• A Mealy machine with polynomial growth of irrational degree
• On the 3-state Mealy Automata over an m-symbol Alphabet of Growth Order [ n ^{{\log n}/{2 \log m}} ]
• Infinite finitely generated automata semigroups have infinite orbits