Groups, Graphs, Languages, and Rewriting

群、图、语言和重写

• 批准号: 2281162
• 金额: --
• 依托单位: Newcastle University
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2281162
• 关键词: Groups; Graphs; Languages; Rewriting

Geometric group theory is the study of the algebraic properties of groups and how they relate to their geometric properties using technology from theoretical computer science, low dimensional topology, hyperbolic geometry and algebra. Properties of interest include those that don't depend on the presentation, including the word problem, the conjugacy problem, the isomorphism problem, and the property of being automatic. The project will investigate decision problems in groups using a combination of methods from rewriting of strings, cycles, trees, terms, (hyper)graphs, simplicial complexes and the theory of formal languages and automata. We relate to previous work of the doctoral student in theoretical computer science on the subject of algebraic graph transformation. We connect this to recent work of Delgado, Ventura, Beeker, Margolis, and Weil that builds on Stallings' theory of folding which has application to problems relating to subgroups, automorphisms of free groups; the more recent work extends this to a larger class of groups, and we will take it much further. Our key objectives are to:1. To investigate the relationship between various classes of formal languages in relation to the word problem in groups: context-free, multiple context-free, Church-Rosser, indexed, context-sensitive, growing context-sensitive, tree-adjoining languages.2. To develop methods to construct subgroup automata and develop algorithms relating to subgroups, using techniques from rewriting theory and coset automata.3. Cyclic rewriting has applications to the conjugacy problem in group theory. It was a recent result of Zantema, Konig, Bruggink that termination of cyclic rewriting systems is undecidable in general, however it is unknown if confluence is undecidable in general, even given a finite, terminating system as input (the equivalent property for strings is decidable via critical pair analysis). This is to be investigated.4. To investigate confluence up to garbage in string rewriting building on the student's previous results for graph rewriting. The student conjectures that local confluence up to garbage of terminating string rewriting systems is decidable on a language class with decidable substring closure, but confluence is not decidable in general, even on regular languages due to a result of Caron. Applications include establishing efficient language recognition, such as the word problem for groups. Development of new technologies in rewriting theory, formal languages, and (coset) automata are novel, allowing new applications in (geometric) group theory to obtain new results and algorithms for solving group theoretic problems.

几何群论是研究群的代数性质以及它们如何使用理论计算机科学，低维拓扑，双曲几何和代数技术与它们的几何性质相关联的研究。感兴趣的属性包括那些不依赖于表示的属性，包括单词问题、共轭问题、同构问题和自动属性。该项目将使用重写字符串，循环，树，术语，（超）图，单纯形复合体以及形式语言和自动机理论的组合方法来研究群体中的决策问题。我们涉及到以前的工作的博士生在理论计算机科学的主题代数图变换。我们连接到最近的工作德尔加多，文图拉，Beeker，马戈利斯，和韦尔的基础上Stallings'理论的折叠已应用到有关的问题，分组，自同构的自由群体;最近的工作扩展到一个更大的类的群体，我们将采取更进一步。我们的主要目标是：1.研究各类形式语言之间的关系，这些形式语言与组中的单词问题有关：上下文无关，多重上下文无关，Church-Rosser，索引，上下文敏感，增长上下文敏感，树邻接语言.利用重写理论和陪集自动机的技术，开发构造子群自动机的方法和开发与子群相关的算法。循环重写在群论中的共轭问题上有应用。Zantema，Konig，Bruggink最近的一个结果是循环重写系统的终止一般是不可判定的，然而，即使给定一个有限的终止系统作为输入（字符串的等价性质是通过临界对分析可判定的），汇流是否一般是不可判定的还是未知的。这是要调查。4.在学生先前的图重写结果的基础上，研究字符串重写中的汇流到垃圾。该学生承认，本地汇合到垃圾终止字符串重写系统是可判定的语言类与可判定的子串闭包，但汇合是不可判定的一般，即使在正规语言由于卡隆的结果。应用程序包括建立有效的语言识别，如组的单词问题。重写理论，形式语言和（陪集）自动机的新技术的发展是新颖的，允许新的应用（几何）群论获得新的结果和算法解决群论问题。