A new hierarchy for automaton semigroups

ABSTRACT. We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviours of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata. We prove that the Order Problem is decidable when the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family.

Authors

• Thibault Godin

Keywords

No keywords are indexed for this paper.