The word and order problems for self-similar and automata groups

DOI10.4171/GGD/560zbMath1496.20056arXiv1710.10109OpenAlexW3037522614MaRDI QIDQ784904

Laurent Bartholdi, Ivan Mitrofanov

Publication date: 3 August 2020

Published in: Groups, Geometry, and Dynamics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.10109

zbMATH Keywords

word problemautomata groupsMinsky machinesself-similar groupscontracting groupsmealy machinesorder problem

Mathematics Subject Classification ID

Geometric group theory (20F65) Cellular automata (computational aspects) (68Q80) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Turing machines and related notions (03D10)

Related Items

Algorithmic aspects of branched coverings. II/V: Sphere bisets and decidability of Thurston equivalence ⋮ An automaton group with undecidable order and Engel problems ⋮ The word problem for finitary automaton groups ⋮ An automaton group with \textsf{PSPACE}-complete word problem ⋮ The lamplighter group of rank two generated by a bireversible automaton ⋮ Unnamed Item ⋮ Generic properties in some classes of automaton groups ⋮ On orbits and the finiteness of bounded automaton groups ⋮ On the existence of free subsemigroups in reversible automata semigroups ⋮ A New Hierarchy for Automaton Semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Orbit automata as a new tool to attack the order problem in automaton groups
• The 4-way deterministic tiling problem is undecidable
• On the Burnside problem for periodic groups
• On Burnside's problem on periodic groups
• On the automorphism group of the one-rooted binary tree
• An automaton group with undecidable order and Engel problems
• Infinite automaton semigroups and groups have infinite orbits
• Implementing Computations in Automaton (Semi)groups
• Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$
• The Nilpotency Problem of One-Dimensional Cellular Automata
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• The undecidability of the domino problem