An Automaton Group with PSPACE-Complete Word Problem
From MaRDI portal
Publication:6320166
DOI10.4230/LIPICS.STACS.2020.6arXiv1906.03424MaRDI QIDQ6320166FDOQ6320166
Authors: Jan Philipp Wächter, Armin Weiß 
Publication date: 8 June 2019
Abstract: We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem and acts over a binary alphabet. Thus, it is optimal in terms of the alphabet size. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D'Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-complete word problem and the second one is to utilize a construction used by Barrington to simulate Boolean circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.
This page was built for publication: An Automaton Group with PSPACE-Complete Word Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320166)
