The finiteness problem for automaton semigroups is undecidable

Abstract

The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.

References in corpus (2)

• Implementing Computations in Automaton (Semi)groups
• The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable

Cited by in corpus (10)

• On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups
• Automaton Semigroups and Groups: On the Undecidability of Problems Related to Freeness and Finiteness
• 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
• Orbit Expandability of Automaton Semigroups and Groups
• On Orbits and the Finiteness of Bounded Automaton Groups
• Preserving self-similarity in free products of semigroups
• On a class of poly-context-free groups generated by automata
• The Word Problem for Finitary Automaton Groups