Algebraic Decision Problems over the Activity Hierarchy of Automaton Structures

自动机结构活动层次的代数决策问题

• 批准号: 492814705
• 负责人: Dr. Jan Philipp Wächter
• 金额: --
• 依托单位: Dep. de Matemática Pura
• 依托单位国家: 德国
• 项目类别: WBP Fellowship
• 财政年份: 2021
• 资助国家: 德国
• 起止时间: 2020-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/492814705?language=en
• 关键词: Algebraic; Decision; Problems; over; Activity

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.

该项目位于理论计算机科学和数学之间的跨学科领域，其目的是为马克斯·德恩（Max Dehn）于1911年发起的关于代数决策问题的漫长而生动的研究路线做出贡献。它的基本思想是研究自相似代数结构（特别是群和半群）上的决策问题的可判定性和复杂性，特别是由有限自动机生成的问题。这些问题的例子包括单词问题，在群的情况下，询问在生成元上的给定单词是否表示中性元素，以及有限性问题，询问给定代数对象是否有限，但还有更多，本项目考虑其中的一些。在世纪后半叶，不仅随着计算机技术的兴起，而且当人们清楚地看到许多具有特殊的，令人惊讶的，奇特的，有时完全怪异的属性似乎有一个自然和简单的介绍使用有限自动机。虽然历史上第一个具有次指数但超多项式增长的群的例子，Grigorchuk群，是这样一个群的最突出的例子，还有更多的自动机生成的结构继续革命性地改变我们对群和其他代数对象的看法。考虑到这一点，这一领域的许多问题--即使是一些看似简单的问题--仍然没有解决也就不足为奇了。本项目的目标是阐明这些悬而未决的问题。在这样做的过程中，它不仅可以增加代数领域的自动机结构的知识，而且还为计算机科学家提供了新的工具和见解，用于代数和其他决策问题。主要考虑决策问题（如Dehn的三个基本问题，但也有自由度和有限性问题以及某些成员问题），关于所谓的活动层次，这是由Sidki在2000年引入的自动机群的分类，通过其生成自动机中的循环结构。最近，Bartholdi，Godin，Klimann和Picantin将这个概念推广到幺半群，目前的项目建议进一步扩展这个概念。此外，该项目还将研究生成自动机的结构如何影响所生成对象的代数结构，反之亦然，只要这对决策问题很有趣。这些问题将通过现有的技术以及需要开发的新技术来解决。