On level-transitivity and exponential growth (Q1702514): Difference between revisions

Given a Mealy automaton $\mathcal{A}$ with both alphabets equal to $\Sigma$, the mappings from $\Sigma^*$ to $\Sigma^*$ induced by states of $\mathcal{A}$ generate a so-called automaton semigroup $\langle\mathcal{A}\rangle_+$. If $\mathcal{A}$ is invertible -- that is, if each state induces a permutation on $\Sigma$ -- then each mapping in $\langle\mathcal{A}\rangle_+$ admits an inverse and $\mathcal{A}$ also defines a so-called automaton group $\langle\mathcal{A}\rangle$. Moreover, reversibility of a Mealy automaton is equivalent to invertibility of its dual. \par The action of an automaton group $\langle\mathcal{A}\rangle$ on $\Sigma^*$ is said to be level-transitive if its restriction to $\Sigma^n$ has a unique orbit for all $n$; the group $\langle\mathcal{A}\rangle$ is then called level-transitive as well. \par The article deals with implications of level-transitivity of the group generated by a dual of some reversible Mealy automaton. It is known [\textit{I. Klimann}, Theory Comput. Syst. 58, No. 4, 664--680 (2016; Zbl 1345.20074)] that if a reversible Mealy automaton $\mathcal{A}$ has a prime number of states, then level-transitivity of the group generated by its dual implies freeness of the semigroup $\langle\mathcal{A}\rangle_+$. The author proves that in case the assumption of a prime number of states is replaced by invertibility of $\mathcal{A}$, then the semigroup $\langle\mathcal{A}\rangle_+$, although not necessarily free, is always of exponential growth. This implies exponential growth for the group $\langle\mathcal{A}\rangle$ as well.