Group Theory Seminar
An Automaton Group with PSPACE-Complete Word Problem
Speaker: Armin Weiß (Universidad de Stuttgart)Date: Thursday, 04 May 2023 - 11:30Place: Aula Gris 3, ICMAT
Abstract:
Finite automata pose an interesting alternative way to present groups and semigroups. Some of these automaton groups, such as the Grigorchuk group, became famous for their peculiar properties and have been extensively studied.
We constructed 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. The construction simulates a computation of a Turing machine in an automaton group. It combines two main ideas: the first one is a construction used by D'Angeli, Rodaro and Wächter 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 circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.
In the talk I will present a proof for PSPACE-hardness if the automaton group is part of the input and will explore some related questions.
The talk is based on joint work with Jan Philipp Wächter.
