Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem

特殊逆幺半群：子群、结构、几何、重写系统和应用题

基本信息

批准号：
EP/N033353/1
负责人：
Robert Gray
金额：
$ 12.82万
依托单位：
University of East Anglia
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2016
资助国家：
英国
起止时间：
2016 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FN033353%2F1
关键词：
Special inverse monoids subgroups structure

项目摘要

This project is concerned with the study of certain fundamental objects in algebra called groups, monoids and inverse monoids. These objects arise naturally in the mathematical study of symmetry and partial symmetry. Given any mathematical structure on a set, the collection of structure-preserving mappings from the set to itself form a monoid, the collection of all symmetries form a group, while the partial symmetries give rise to an inverse monoid. In this way these algebraic objects pervade mathematics. One way to represent a group, monoid of inverse monoid is via a presentation. The elements are represented by strings of letters, called words. We are also given a set of pairs of words, called defining relations, which are rules telling us that certain pairs of words are equal to each other. Then two words are defined to be equal if one can be turned into the other by a sequence of applications of the defining relations. For example, using the alphabet with the letters a and b, and just with a single defining relation ab=ba, the words aba and aab are equal since aba = a(ba) = a(ab) = aab. On the other hand, the words bb and ab are not equal since one cannot be transformed into the other using the relation ab=ba. A famous result in twentieth century mathematics shows that there does not exist, in general, an algorithm to decide whether two words are equal in a monoid defined by a finite presentation. This is known as the word problem, and is also undecidable in general both for finitely presented groups and inverse monoids. These results are important since they were some of the first concrete natural decision problems proven to be undecidable in general. The importance of the word problem is clear: decidability of the word problem for a class of algebras indicates that we have some hope of studying the structural properties of algebras in the class, while undecidability of the word problem would suggest there would likely to be major difficulties in investigating the class as a whole.Given that the word problem is undecidable in general, a lot of research has been done to identify classes of monoids for which the word problem is decidable. One fundamental idea is that by restricting the number of defining relations in the presentation, this should limit the complexity of the object that it defines. An important result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. In contrast to this, the following problem remains open:Open problem. Is the word problem decidable for monoids with a single defining relation? This important problem has been open for more than half a century, and is one of the main motivations for our research project. Rather than attacking this problem directly, the project instead aims to develop various aspects of the theory of certain inverse monoids, called special inverse monoids. Specifically the project will develop certain important tools from theoretical computer science, from the area of rewriting systems, to investigate the subgroups, structure, and geometry of these inverse monoids. We will then apply this theory to investigate the word problem for these inverse monoids which will then lead to important results about decidability of the word problem, in general, for monoids defined by a single defining relation. The project will involve extensive collaboration with researchers both from the UK and from universities in Portugal, Serbia and the USA. We will organise a workshop midway through the project, centred around its main themes, which will bring together leading experts from a diverse range of topics in algebra, logic and theoretical computer science.

该项目涉及代数中某些称为群、幺半群和逆幺半群的基本对象的研究。这些物体在对称性和部分对称性的数学研究中自然出现。给定集合上的任何数学结构，从集合到自身的结构保持映射的集合形成幺半群，所有对称性的集合形成群，而部分对称性产生逆幺半群。通过这种方式，这些代数对象遍及数学。表示群、幺半群或反幺半群的一种方法是通过演示。这些元素由称为单词的字母串表示。我们还得到了一组单词对，称为定义关系，这些规则告诉我们某些单词对彼此相等。然后，如果通过一系列定义关系的应用可以将一个单词变成另一个单词，则两个单词被定义为相等。例如，使用带有字母 a 和 b 的字母表，并且仅使用单个定义关系 ab=ba，单词 aba 和 aab 是相等的，因为 aba = a(ba) = a(ab) = aab。另一方面，单词 bb 和 ab 不相等，因为一个不能使用关系 ab=ba 转换为另一个。二十世纪数学中的一个著名结果表明，一般来说，不存在一种算法来确定两个单词在由有限表示定义的幺半群中是否相等。这被称为文字问题，并且对于有限呈现群和逆幺半群来说通常也是不可判定的。这些结果很重要，因为它们是第一个被证明一般情况下不可判定的具体自然决策问题。应用题的重要性是显而易见的：应用题对于一类代数的可判定性表明我们有希望研究该类代数的结构性质，而应用题的不可判定性则表明可能存在重大问题。考虑到词问题一般是不可判定的，人们进行了大量的研究来识别词问题可判定的幺半群类。一个基本思想是，通过限制表示中定义关系的数量，这应该限制其定义的对象的复杂性。对于群来说，这种类型的一个重要结果是马格努斯定理，它表明由单一定义关系定义的群都具有可判定的词问题。与此相反，以下问题仍然悬而未决：开放问题。对于具有单一定义关系的幺半群，这个词问题是否可判定？这个重要的问题已经开放了半个多世纪，也是我们研究项目的主要动机之一。该项目不是直接解决这个问题，而是旨在发展某些逆幺半群理论的各个方面，称为特殊逆幺半群。具体来说，该项目将从理论计算机科学、重写系统领域开发某些重要工具，以研究这些逆幺半群的子群、结构和几何。然后，我们将应用这个理论来研究这些逆幺半群的单词问题，这将导致关于单词问题的可判定性的重要结果，一般来说，对于由单一定义关系定义的幺半群。该项目将涉及与英国以及葡萄牙、塞尔维亚和美国大学的研究人员的广泛合作。我们将在项目中途组织一次研讨会，围绕其主题，汇集来自代数、逻辑和理论计算机科学等不同主题的领先专家。