THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
From MaRDI portal
Publication:5410736
DOI10.1142/S0218196714500015zbMath1292.20040arXiv1304.2295MaRDI QIDQ5410736
Publication date: 17 April 2014
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.2295
Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Groups acting on trees (20E08)
Related Items (31)
Crisp-determinization of weighted tree automata over strong bimonoids ⋮ On the complexity of the word problem for automaton semigroups and automaton groups ⋮ Corrigendum to: ``Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ Automaton semigroups: the two-state case. ⋮ Freeness of automaton groups vs boundary dynamics ⋮ A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group ⋮ Automaton groups and complete square complexes ⋮ Orbit automata as a new tool to attack the order problem in automaton groups ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ An automaton group with undecidable order and Engel problems ⋮ Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$ ⋮ The word problem for finitary automaton groups ⋮ A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group ⋮ On a class of poly-context-free groups generated by automata ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ Automaton (Semi)groups: Wang Tilings and Schreier Tries ⋮ Automaton semigroups: new constructions results and examples of non-automaton semigroups ⋮ Algorithmic Decidability of Engel’s Property for Automaton Groups ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Generic properties in some classes of automaton groups ⋮ On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata ⋮ On orbits and the finiteness of bounded automaton groups ⋮ Orbit expandability of automaton semigroups and groups ⋮ Automaton semigroup constructions. ⋮ Infinite automaton semigroups and groups have infinite orbits ⋮ Graph automaton groups ⋮ The word and order problems for self-similar and automata groups ⋮ On the structure theory of partial automaton semigroups ⋮ A New Hierarchy for Automaton Semigroups
Cites Work
- On exponential growth and uniformly exponential growth for groups.
- The conjugacy problem in automaton groups is not solvable.
- On a question of Atiyah
- On the Limit Sets of Cellular Automata
- ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
- Periodicity and Immortality in Reversible Computing
- ON THE CAYLEY SEMIGROUP OF A FINITE APERIODIC SEMIGROUP
- The Nilpotency Problem of One-Dimensional Cellular Automata
- The lamplighter group as a group generated by a 2-state automaton, and its spectrum
This page was built for publication: THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
