The finiteness problem for automaton semigroups is undecidable.
From MaRDI portal
Groups acting on trees (20E08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)
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.
Recommendations
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
- Permutive one-way cellular automata and the finiteness problem for automaton groups
- Automaton (semi)groups: Wang tilings and Schreier tries
Cites work
- ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
- On a question of Atiyah
- On exponential growth and uniformly exponential growth for groups.
- ON THE CAYLEY SEMIGROUP OF A FINITE APERIODIC SEMIGROUP
- On the Limit Sets of Cellular Automata
- Periodicity and Immortality in Reversible Computing
- The conjugacy problem in automaton groups is not solvable.
- The lamplighter group as a group generated by a 2-state automaton, and its spectrum
- The Nilpotency Problem of One-Dimensional Cellular Automata
Cited in
(34)- An automaton group with undecidable order and Engel problems
- Permutive one-way cellular automata and the finiteness problem for automaton groups
- Corrigendum to: ``Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Automaton groups and complete square complexes
- Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
- Generic properties in some classes of automaton groups
- Orbit expandability of automaton semigroups and groups
- Infinite automaton semigroups and groups have infinite orbits
- On the complexity of the word problem for automaton semigroups and automaton groups
- Freeness of automaton groups vs boundary dynamics
- On a class of poly-context-free groups generated by automata
- An automaton group with \textsf{PSPACE}-complete word problem
- On torsion-free semigroups generated by invertible reversible Mealy automata
- Automaton semigroups: the two-state case.
- Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V
- A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
- Automaton (semi)groups: Wang tilings and Schreier tries
- A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
- On orbits and the finiteness of bounded automaton groups
- Crisp-determinization of weighted tree automata over strong bimonoids
- On the orbits of automaton semigroups and groups
- Automatic semigroups vs automaton semigroups
- Graph automaton groups
- Automaton semigroups: new constructions results and examples of non-automaton semigroups
- Algorithmic decidability of Engel's property for automaton groups
- A new hierarchy for automaton semigroups
- The word problem for finitary automaton groups
- Preserving self-similarity in free products of semigroups
- Finiteness problem for automaton groups over a binary alphabet is almost decidable
- The freeness problem for automaton semigroups
- Automaton semigroup constructions.
- The word and order problems for self-similar and automata groups
- On the structure theory of partial automaton semigroups
- Orbit automata as a new tool to attack the order problem in automaton groups
This page was built for publication: The finiteness problem for automaton semigroups is undecidable.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410736)
