On level-transitivity and exponential growth (Q1702514): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q115608644, #quickstatements; #temporary_batch_1711565664090 |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / arXiv ID | |||
Property / arXiv ID: 1605.09579 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Implementing Computations in Automaton (Semi)groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automata and square complexes. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Groups of intermediate growth: an introduction. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2702125 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2783052 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automaton semigroups: the two-state case. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3111128 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2944019 / rank | |||
Normal rank |
Latest revision as of 06:37, 15 July 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
0 references