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

DOI10.4171/GGD/560zbMATH Open1496.20056arXiv1710.10109OpenAlexW3037522614MaRDI QIDQ784904FDOQ784904

Authors: Laurent Bartholdi, Ivan Mitrofanov 

Publication date: 3 August 2020

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

Abstract: We prove that the word problem is undecidable in functionally recursive groups, and that the order problem is undecidable in automata groups, even under the assumption that they are contracting.

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

Recommendations

• An automaton group with undecidable order and Engel problems
• The conjugacy problem in automaton groups is not solvable.
• scientific article; zbMATH DE number 3959758
• scientific article; zbMATH DE number 67424

zbMATH Keywords

Minsky machinesword problemautomata groupsself-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)

Cites Work

• Title not available (Why is that?)
• On the Burnside problem for periodic groups
• On Burnside's problem on periodic groups
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Title not available (Why is that?)
• The undecidability of the domino problem
• Automata, dynamical systems, and groups
• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• The finiteness problem for automaton semigroups is undecidable.
• On the automorphism group of the one-rooted binary tree
• Orbit automata as a new tool to attack the order problem in automaton groups
• Title not available (Why is that?)
• An automaton group with undecidable order and Engel problems
• The 4-way deterministic tiling problem is undecidable
• Infinite automaton semigroups and groups have infinite orbits
• Some undecidability results for asynchronous transducers and the Brin-Thompson group \(2V\)

Cited In (19)

• The conjugacy problem in automaton groups is not solvable.
• Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation
• A language hierarchy and kitchens-type theorem for self-similar groups
• On orbits and the finiteness of bounded automaton groups
• Title not available (Why is that?)
• An automaton group with undecidable order and Engel problems
• A new hierarchy for automaton semigroups
• Algorithmic aspects of branched coverings. II/V: Sphere bisets and decidability of Thurston equivalence
• The word problem for finitary automaton groups
• Orbit automata as a new tool to attack the order problem in automaton groups
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Undecidability of the centers of groups and group algebras.
• Generic properties in some classes of automaton groups
• Title not available (Why is that?)
• The lamplighter group of rank two generated by a bireversible automaton
• On the existence of free subsemigroups in reversible automata semigroups
• On the orbits of automaton semigroups and groups
• An automaton group with \textsf{PSPACE}-complete word problem
• Some undecidability results for asynchronous transducers and the Brin-Thompson group \(2V\)

This page was built for publication: The word and order problems for self-similar and automata groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q784904)