Orbit expandability of automaton semigroups and groups (Q2290646)

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.