Orbit expandability of automaton semigroups and groups (Q2290646): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:37, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orbit expandability of automaton semigroups and groups |
scientific article |
Statements
Orbit expandability of automaton semigroups and groups (English)
0 references
29 January 2020
0 references
The article studies several problems related to orbital growth in automaton semigroups and groups, where automaton semigroups are understood to be generated by \textit{partial} deterministic letter-to-letter transducers. Consider an automaton semigroup \(S\) acting on \(\Sigma^*\) and for each \(w \in \Sigma^*\) denote by \(Sw\) the orbit of \(w\) with respect to \(S\). A word \(u \in \Sigma^*\) is said to be \(k\)-expandable with respect to \(S\) if there exists \(v \in \Sigma^+\) such that \(\lvert Suv\rvert \geq \lvert Su\rvert + k\) and expandable if it is \(k\)-expandable for some \(k \geq 1\). This notion is motivated by the study of \(\omega\)-words with infinite orbits, as all prefixes of these ones are clearly expandable. In the main result of the article, the authors prove that, given a transducer \(\mathcal{T}\) generating an automaton semigroup \(S\), a word \(u \in \Sigma^*\) and a natural number \(k\), it is decidable whether \(u\) is \(k\)-expandable with respect to \(S\). A space-bounded nondeterministic decision procedure is described for this problem, while the Immerman-Szelepcsényi inductive counting technique is employed in its analysis [\textit{N. Immerman}, SIAM J. Comput. 17, No. 5, 935--938 (1988; Zbl 0668.68056); \textit{R. Szelepcsényi}, Acta Inf. 26, No. 3, 279--284 (1988; Zbl 0638.68046)]. The results for automaton semigroups are further strengthened in the case of an automaton \textit{group} \(G\). The authors prove an algebraic characterisation of expandable words with respect to \(G\), which they use to obtain a more efficient decision procedure for this particular case. It is also proved that every word is expandable in an automaton semigroup generated by a complete reversible transducer.
0 references
automaton semigroup
0 references
automaton group
0 references
orbital growth
0 references
expandable word
0 references
decidability
0 references