Solving word problems via generalisations of small cancellation

这个项目是关于群论的。群论是研究对称性的学科，对称性是形成一个群的任何物体的对称性的集合，有着广泛的应用。例如，现代纠错码-例如用于将数据存储到CD上-使用群论，而将群论应用于数据加密是一个非常活跃的研究课题。描述一个群体的一种方式是通过演示。组的元素由字母串表示，称为单词。然而，有些单词对在组中是相等的：这些相等是由组中与空词相等的单词列表确定的，称为关系词。这是群在许多情况下自然产生的方式：例如在拓扑学中，当研究流形的基本群时。这也是在计算机上处理无限群的为数不多的方法之一，因为计算机可以通过有限表示的方式被告知无限多个群元素。二十世纪数学中最著名的结果之一证明，一般来说，不存在一种算法来确定两个单词在组中何时相等。这个问题--问题这个词--是第一批被证明在一般情况下是不可判定的具体决策问题之一；它表明，不完备性等概念并不纯粹具有哲学意义。然而，这并不意味着问题不能在特殊情况下解决，它的解决对于发展对一大类无限群的具体理解是必不可少的。这个项目寻求开发一种新的方式来思考这些群体，从而为他们中的许多人带来快速、实用的算法。我们将使用一种称为范坎本图的图片来处理这些群体，该图由点(顶点)、它们之间的线(边)和由线包围的区域组成。每条边都标有一个单词，这样沿着其中一个区域一直读下去，就会得到该组的一个相关者。将区域拼接在一起可以被认为是一种拼图游戏，其中两个区域只有在它们的一条边彼此一致的情况下才能并排放置。我们将开发实用的算法，以一组关系器作为输入，并证明所有可以由它们制成的图相对于外边界周围的单词长度来说，只有相当少的区域。由此推论，如果一个词在组中等于空词，则这可以在相应较短的步骤中显示。要开发这些算法，将需要进行大量的理论探索：例如，我们需要确定我们将研究的组类和自动组类之间的关系，对于这两类自动组，已证明一种非常不同的方法是成功的。我们还将把我们的工作扩展到比有限呈现群更广泛的一类代数结构，包括么半群和矩阵群。这项工作将有几个应用和好处，其中一些在群论中，另一些则在相当远的地方。我们将把我们的软件作为计算机代数系统GAP的一部分免费提供，这样即使是不知道我们的技术的用户也会注意到在广泛的相关算法中性能的提高。能够在计算机上输入一组数据，并快速获得关于其结构的答案，这使研究人员能够进行实验和形成猜测。此外，将这些方法集成到更大的软件套件中意味着其他领域的研究人员可以使用依赖群论技术的方法，而不需要了解任何群论，从而促进了整个学科范围的快速发展，从应用程序，如陪集计数，到纯数学领域，如拓扑学，再到更遥远的学科，如化学和物理。

This project is concerned with group theory. Group theory is the study of symmetry - the set of symmetries of any object form a group - and has wide-ranging applications. For example, modern error-correcting codes - such as are used for storing data onto CDs - use group theory, and the application of group theory to the encryption of data is an extremely active research topic. One way to describe a group is via a presentation. Elements of the group are represented by strings of letters, called words. However, some of the pairs of words are equal in the group: these equalities are determined by a list of words that are equal in the group to the empty word, called relators. This is the way that groups naturally arise in many contexts: for example in topology, when studying fundamental groups of manifolds. It is also one of the few ways of working with an infinite group on a computer, as the computer can be told about the infinitely many group elements by means of a finite presentation. One of the most famous results in twentieth century mathematics proves that, in general, there cannot exist an algorithm to decide when two words are equal in the group. This problem - the word problem - was one of the first concrete decision problems proven to be undecidable in general; and showed that notions such as incompleteness are not of purely philosophical interest. However, that does not mean that the word problem cannot be solved in special cases, and its solution is essential to the development of a concrete understanding of a wide class of infinite groups. This project seeks to develop a new way of thinking about these groups, leading to fast-running, practical algorithms for many of them.We will work with these groups by using a type of picture called a van Kampen diagram, which consists of dots (vertices), lines between them (edges), and regions enclosed by the lines. Each edge is labelled with a word, such that reading all of the way around one of the regions gives one of the relators of the group. Fitting regions together can be thought of as a kind of jigsaw puzzle, where two regions can be put side-by-side only if they agree with each other along one of their edges. We will develop practical algorithms which take as input a set of relators, and prove that all diagrams that can be made from them have only a fairly small number of regions, relative to the length of the word around the outer boundary. From this it follows that if a word is equal in the group to the empty word, then this can be shown in a correspondingly short number of steps. To develop these algorithms, a considerable amount of theoretical exploration will be required: for example, we need to determine the relationship between the class of groups that we will study and the class of automatic groups, for which a very different approach has been shown to be successful. We will also extend our work to a wider class of algebraic structures than finitely-presented groups, including monoids and matrix groups. This work will have several applications and benefits, some of them inside group theory and others considerably further afield. We will make our software available as part of the computer algebra system GAP, which is freely available, so that even users who are unaware of our techniques will notice improved performance in a wide range of related algorithms. Being able to input a group on a computer and rapidly get answers about its structure enables researchers to experiment and form conjectures. Furthermore, integrating such methods into larger suites of software means that researchers in other areas can use methods which rely on group-theoretic techniques without needing to know any group theory, facilitating rapid progress in a whole range of disciplines, from applications such as coset enumeration, to pure mathematical areas such as topology, to more distant subjects such as chemistry and physics.