Orbit expandability of automaton semigroups and groups (Q2290646): Difference between revisions

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.