Algebraic Decision Problems over the Activity Hierarchy of Automaton Structures

• Applicant: Dr. Jan Philipp Wächter
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2021 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 492814705

Set in the interdisciplinary area between Theoretical Computer Science and Mathematics, the aim of the proposed project is to contribute to the long and vivid research line on algebraic decision problems initiated already in 1911 by the seminal work of Max Dehn. Its fundamental idea is to investigate questions on the decidability and complexity of decision problems over self-similar algebraic structures (in particular, groups and semigroups) and, in particular, those generated by finite automata. Examples for these problems include the word problem, which, in the group case, asks whether a given word over the generators represents the neutral element, and the finiteness problem asking whether a given algebraic object is finite, but there are many more and this project considers some of them.The use of automata, which originate in the theory of Computer Science, to present rather mathematical algebraic objects gained a lot of interest in the second half of the 20th century not only with the rise of computer technology but also when it became clear that many complex groups with special, surprising, peculiar and sometimes outright weird properties seem to have a natural and simple presentation using a finite automaton. While the historically first example of a group with subexponential but superpolynomial growth, the Grigorchuk group, is the most prominent example of such a group, there are many more and structures generated by automata continue to revolutionize our perspective on groups and other algebraic objects to this day. With this in mind, it comes as no surprise that many problems in this area – even some seemingly simple ones – remain open.The objective of this project is to shed some light on these open problems. In doing so, it cannot only increase the knowledge on automaton structures for the field of algebra but also provide new tools and insights for Computer Scientists working on algebraic and other decision problems. Primary consideration will be given to decision problems (such as Dehn's three fundamental ones but also the freeness and finiteness problems as well as certain membership problems) with respect to the so-called activity hierarchy, which was introduced by Sidki in 2000 as a classification of automaton groups by the structures of the cycles in their generating automata. Recently, the notion has been generalized to monoids by Bartholdi, Godin, Klimann and Picantin and the current project proposes to extend this notion even further. Additionally, the project will also investigate how the structure of the generating automaton affects the algebraic structure of the generated object and vice-versa, as far as this is interesting with respect to decision problems. These questions will be addressed by existing but also new techniques that need to be developed.

• DFG Programme: WBP Fellowship
• International Connection: Italy
• Host: Professor Dr. Emanuele Rodaro