We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE.
- Authors
GILLIBERT, PIERRE
- 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 a Mealy automaton, such that the plane admits a valid Wang tiling if and only if the Mealy automaton generates a infinite semi-group. The construction is similar to a construction by Kari for proving that the nilpo-tency 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 finite-ness problem for automaton semigroups is undecidable.
- Subjects
ROBOTS; SEMIGROUPS (Algebra); FINITE element method; INFINITY (Mathematics); TILING (Mathematics)
- Publication
International Journal of Algebra & Computation, 2014, Vol 24, Issue 1, p1
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196714500015