The Finiteness Problem for Automaton Semigroups of Extended Bounded Activity
Solves an open problem in the theory of automaton semigroups for researchers in algebraic automata theory.
The paper extends the notion of activity for automaton semigroups and monoids, proving that the finiteness problem is decidable for complete automaton semigroups and monoids of bounded activity, solving an open problem. The result also covers finitely generated subsemigroups.
We extend the notion of activity for automaton semigroups and monoids introduced by Bartholdi, Godin, Klimann and Picantin to a more general setting. Their activity notion was already a generalization of Sidki's activity hierarchy for automaton groups. We show that the language of $ω$-words with infinite orbits is effectively a deterministic Büchi language for automata with bounded extended activity, which yields decidability of the finiteness problem for complete automaton semigroups and monoids of bounded activity (solving an open problem by Bartholdi, Godin, Klimann and Picantin). In fact, we obtain a stronger result also covering finitely generated subsemigroups.