Algebraic Decision Problems over the Activity Hierarchy of Automaton Structures

设置在理论计算机科学和数学之间的跨学科领域，提出的项目的目的是促进代数决策问题的长而生动的研究线已经在1911年由马克斯·德恩的开创性工作发起。它的基本思想是研究自相似代数结构（特别是群和半群）上决策问题的可决性和复杂性问题，特别是由有限自动机产生的决策问题。这些问题的例子包括词问题，在组的情况下，问一个给定的词在生成器上是否代表中性元素，以及有限性问题，问一个给定的代数对象是否有限，但还有更多的问题，本项目考虑其中的一些。自动机起源于计算机科学理论，在20世纪下半叶，随着计算机技术的兴起，许多具有特殊的、令人惊讶的、奇特的、有时甚至是完全奇怪的性质的复杂群体似乎使用有限自动机有一个自然而简单的表示，自动机的使用引起了人们的极大兴趣。虽然历史上第一个具有亚指数但超多项式增长的群的例子，Grigorchuk群，是这种群的最突出的例子，但还有更多的例子和自动机产生的结构，直到今天仍在继续改变我们对群和其他代数对象的看法。考虑到这一点，这一领域的许多问题——甚至一些看似简单的问题——仍然存在就不足为奇了。这个项目的目的是阐明这些悬而未决的问题。在此过程中，它不仅增加了代数领域的自动机结构知识，而且为从事代数和其他决策问题的计算机科学家提供了新的工具和见解。主要考虑的是关于所谓的活动层次结构的决策问题（如Dehn的三个基本问题，以及自由和有限问题以及某些成员问题），这是Sidki在2000年引入的，作为自动机群体的分类，通过它们产生的自动机中的循环结构。最近，这个概念被Bartholdi， Godin， Klimann和Picantin推广到一元群，目前的项目提议进一步扩展这个概念。此外，该项目还将研究生成自动机的结构如何影响生成对象的代数结构，反之亦然，因为这与决策问题有关。这些问题将通过现有的但也需要开发的新技术来解决。

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.