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

DOI10.1007/S00224-021-10064-7MaRDI QIDQ2701072zbMATH OpenOpenAlexFDO

Authors Jan Philipp Wächter, Armin Weiß

Publication date 27 April 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\textsf{PSPACE}automaton groupcompressed word problemword problem

Mathematics Subject Classification ID

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

Cites work

• A Property of Finite Simple Non-Abelian Groups
• An automaton group with undecidable order and Engel problems
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Codes and automata.
• Complexity and randomness in group theory. GAGTA book 1
• Computational Complexity
• Groups of intermediate growth: an introduction.
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Growth of Schreier graphs of automaton groups.
• scientific article; zbMATH DE number 3810927 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• scientific article; zbMATH DE number 3231933 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 7650891 (Why is no real title available?)
• On a free group of transformations defined by an automaton.
• On Burnside's problem on periodic groups
• On some algorithmic properties of finite state automorphisms of rooted trees.
• On the complexity of the word problem for automaton semigroups and automaton groups
• On the structure theory of partial automaton semigroups
• Realizing complex boolean functions with simple groups
• The Compressed Word Problem for Groups
• The conjugacy problem in automaton groups is not solvable.
• The finiteness problem for automaton semigroups is undecidable.
• The word and order problems for self-similar and automata groups
• The word problem
• The word problem in Hanoi Towers groups.

Cited in

(5)

• The word problem for finitary automaton groups
• Compressed decision problems in hyperbolic groups
• Preserving self-similarity in free products of semigroups
• The word problem and growth of groups
• The finiteness problem for automaton semigroups of extended bounded activity

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

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