THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
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 a Mealy automaton, such …