An Automaton Group with PSPACE-Complete Word Problem

Abstract: Finite automata pose an interesting alternative way to present groups and semigroups. Some of these automaton groups became famous for their peculiar properties and have been extensively studied.

One aspect of this research is the study of algorithmic properties of automaton groups and semigroups. While many natural algorithmic decision problems have been proven or are generally suspected to be undecidable for these classes, the word problem forms a notable exception. In the group case, it asks whether a given word in the generators is equal to the neutral element in the group in question and is well-known to be decidable for automaton groups. In fact, it was observed in a work by Steinberg published in 2015 that it can be solved in nondeterministic linear space using a straight-forward guess and check algorithm. In the same work, he conjectured that there is an automaton group with a PSPACE-complete word problem.

In a recent paper presented at STACS 2020, Jan Philipp Wächter and myself could prove that there indeed is such an automaton group. To achieve this, we combined two ideas. The first one is a construction introduced by D'Angeli, Rodaro and Wächter to show that there is an inverse automaton semigroup with a PSPACE-complete word problem and the second one is an idea already used by Barrington in 1989 to encode NC¹ circuits in the group of even permutation over five elements. In the talk, we will discuss how Barrington's idea can be applied in the context of automaton groups, which will allow us to prove that the uniform word problem for automaton groups (were the generating automaton and, thus, the group is part of the input) is PSPACE- complete. Afterwards, we will also discuss the ideas underlying the construction to simulate a PSPACE- machine with an invertible automaton, which allow for extending the result to the non-uniform case. Finally, we will briefly look at related problems such as the compressed word problem for automaton groups and the special case of automaton group of polynomial activity.

group theory

Audience: researchers in the discipline

Symmetry in Newcastle