Orbit expandability of automaton semigroups and groups

DOI10.1016/J.TCS.2019.12.037MaRDI QIDQ2290646zbMATH OpenOpenAlexWikidataFDO

Authors Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.07359

automaton group automaton semigroup decidability expandable word orbital growth

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Abstract: We introduce the notion of expandability in the context of automaton semigroups and groups: a word is k-expandable if one can append a suffix to it such that the size of the orbit under the action of the automaton increases by at least k. This definition is motivated by the question which {omega}-words admit infinite orbits: for such a word, every prefix is expandable. In this paper, we show that, on input of a word u, an automaton T and a number k, it is decidable to check whether u is k-expandable with respect to the action of T. In fact, this can be done in exponential nondeterministic space. From this nondeterministic algorithm, we obtain a bound on the length of a potential orbit-increasing suffix x. Moreover, we investigate the situation if the automaton is invertible and generates a group. In this case, we give an algebraic characterization for the expandability of a word based on its shifted stabilizer. We also give a more efficient algorithm to decide expandability of a word in the case of automaton groups, which allows us to improve the upper bound on the maximal orbit-increasing suffix length. Then, we investigate the situation for reversible (and complete) automata and obtain that every word is expandable with respect to these automata. Finally, we give a lower bound example for the length of an orbit-increasing suffix.

Review text

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Orbit expandability of automaton semigroups and groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290646)