An automaton group with \textsf{PSPACE}-complete word problem

DOI10.1007/s00224-021-10064-7OpenAlexW4225825909MaRDI QIDQ2701072

Jan Philipp Wächter, Armin Weiß

Publication date: 27 April 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-021-10064-7

zbMATH Keywords

word problemautomaton group\textsf{PSPACE}compressed word problem

Mathematics Subject Classification ID

Theory of computing (68Qxx) Special aspects of infinite or finite groups (20Fxx) Structure and classification of infinite or finite groups (20Exx)

Related Items (1)

The word problem for finitary automaton groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Growth of Schreier graphs of automaton groups.
• The word and order problems for self-similar and automata groups
• On the structure theory of partial automaton semigroups
• Groups of intermediate growth: an introduction.
• On Burnside's problem on periodic groups
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• An automaton group with undecidable order and Engel problems
• The conjugacy problem in automaton groups is not solvable.
• On the complexity of the word problem for automaton semigroups and automaton groups
• On a free group of transformations defined by an automaton.
• Complexity and Randomness in Group Theory
• The word problem in Hanoi Towers groups
• Computational Complexity
• A Property of Finite Simple Non-Abelian Groups
• The Compressed Word Problem for Groups
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• Realizing complex boolean functions with simple groups
• The word problem

This page was built for publication: An automaton group with \textsf{PSPACE}-complete word problem