We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Automaton Group with PSPACE-Complete Word Problem.
- Authors
Wächter, Jan Philipp; Weiß, Armin
- 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.
- Subjects
ROBOTS; LOGIC circuits; TURING machines; PERMUTATION groups; VOCABULARY
- Publication
Theory of Computing Systems, 2023, Vol 67, Issue 1, p178
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-021-10064-7