Automaton Structures: Structure Theory and Decision Problems

Automata pose a simple way to describe groups and semigroups with sometimes surprisingly complex behavior. A typical example for this behavior is the famous Grigorchuk group, the historical first example of a group of subexponential but superpolynomial growth. It is not finitely presented – in the sense of classical presentations using generators and relations – but it is generated by a finite automaton with five states and binary alphabet. In addition to the many famous and notorious examples of automaton groups, the tension between the simplicity of automaton presentations and the complexity of the generated structures is one of the main reasons to study the class of automaton groups. In recent years, this interest seems to have extended more and more also to automaton semigroups. In the talk, we will first recapitulate the definition of automaton semigroups and group and then discuss them from two angles: the theory of their structure and algebraic decision problems for them. In both cases, we will discuss some open problems and some recent results. In the first part on the structure theory, we will put an emphasis on the connection between partial and complete automata and also discuss the orbits of automaton semigroups and groups. In the second part, we will discuss the current research situation for typical decision problems: Dehn's three fundamental problems (word problem, conjugacy problem and isomorphism problem), the finiteness problem, the freeness problem and some further problems.

Date and Venue

Start Date
Online Zoom meeting
End Date


Jan Philipp Wächter

Speaker's Institution

Institut für Formale Methoden der Informatik (FMI), Universität Stuttgart



Semigroups, Automata and Languages