Algebraic Decision Problems over the Activity Hierarchy of Automaton Structures

该项目设置在理论计算机科学和数学之间的交叉学科领域，其目的是为1911年由Max Dehn的开创性工作开创的关于代数决策问题的漫长而生动的研究路线做出贡献。它的基本思想是研究自相似代数结构(特别是群和半群)上决策问题的可判定性和复杂性问题，特别是由有限自动机生成的决策问题。这些问题的例子包括单词问题，在群的情况下，它询问给定的词是否表示中性元素，以及有限性问题，询问给定的代数对象是否有限，但还有更多的问题，本项目考虑其中的一些。自动机的使用，起源于计算机科学的理论，来表示相当数学的代数对象在20世纪下半叶获得了许多兴趣，不仅随着计算机技术的兴起，而且当人们清楚地发现，许多具有特殊的、令人惊讶的、奇怪的、有时完全奇怪的性质的复杂群似乎具有使用有限自动机的自然而简单的表示时。虽然历史上第一个具有次指数但超多项式增长的群，Grigorchuk群，是这种群的最突出的例子，但还有更多的例子，由自动机生成的结构继续革命性地改变我们对群和其他代数对象的看法，直到今天。考虑到这一点，这一领域的许多问题--甚至一些看似简单的问题--仍然悬而未决也就不足为奇了。这个项目的目标是阐明这些悬而未决的问题。这样做，不仅增加了代数领域关于自动机结构的知识，而且为从事代数和其他决策问题的计算机科学家提供了新的工具和见解。主要考虑与所谓的活动层次有关的决策问题(例如Dehn的三个基本问题，但也包括自由性和有限性问题以及某些成员问题)。活动层次是由Sidki在2000年引入的，它是根据自动机群的生成自动机的圈的结构对自动机群进行分类的。最近，Bartholdi、Godin、Klimann和Picantn已将这一概念推广到么半群，目前的项目建议进一步扩展这一概念。此外，该项目还将调查生成自动机的结构如何影响生成对象的代数结构，反之亦然，就决策问题而言，这是有趣的。这些问题将通过现有的但也需要开发的新技术来解决。

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.