On level-transitivity and exponential growth (Q1702514): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: GAP / rank | |||
Normal rank |
Revision as of 17:42, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On level-transitivity and exponential growth |
scientific article |
Statements
On level-transitivity and exponential growth (English)
0 references
28 February 2018
0 references
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.
0 references
automaton group
0 references
Mealy automaton
0 references
growth of a group
0 references
level-transitivity
0 references