On the Finiteness Problem for Automaton (Semi)groups

Abstract

This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure.

References in corpus (3)

• Implementing Computations in Automaton (Semi)groups
• On the Finiteness Problem for Automaton (Semi)groups
• The smallest Mealy automaton of intermediate growth

Cited by in corpus (11)

• The finiteness problem for automaton semigroups is undecidable
• On the Finiteness Problem for Automaton (Semi)groups
• Implementing Computations in Automaton (Semi)groups
• On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups
• A geometric approach to (semi)-groups defined by automata via dual transducers
• Automaton Semigroups and Groups: On the Undecidability of Problems Related to Freeness and Finiteness
• The growth rates of automaton groups generated by reset automata
• On the Structure Theory of Partial Automaton Semigroups
• Algorithmic decidability of Engel's property for automaton groups
• Infinite Automaton Semigroups and Groups Have Infinite Orbits
• Automorphisms of shift spaces and the Higman--Thompson groups: the one-sided case