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

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

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.