权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Solving word problems via generalisations of small cancellation

通过小消去的泛化解决应用题

基本信息

批准号：
EP/I03582X/1
负责人：
Colva Roney-Dougal
金额：
$ 56.64万
依托单位：
University of St Andrews
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2011
资助国家：
英国
起止时间：
2011 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FI03582X%2F1
关键词：
Solving word problems via generalisations

项目摘要

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.

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