Algorithmic problems in groups and semigroups

群和半群的算法问题

• 批准号: 9970471
• 负责人: John Meakin
• 金额: $ 7.34万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970471&HistoricalAwards=false
• 关键词: Algorithmic; problems; groups; semigroups

MEAKIN(9970471) and SAPIR(9978802)This proposal is a collaborative proposal between researchers at the University of Nebraska-Lincoln and Vanderbilt University. The PI's will consider several algorithmic problems associated with presentations of groups and semigroups. In particular they will use recent results on Higman type embeddings of free Burnside groups into finitely presented groups in order to construct an infinite torsion group with a finite number of generators and a finite number of relations. They will also use these embedding results to study computational complexity by algebraic means. In a second set of problems, they will study connections between residually finite extensions of free groups and their connection with dynamics of polynomial maps over p-adic numbers. A third set of problems is concerned with use of automata-theoretic methods to study algorithmic problems about subgroups of various classes and associated problems. A fourth set of problems is concerned with the study of diagram groups---groups that arise naturally in connection with semigroup presentations.Groups and semigroups are algebraic objects that arise ubiquitously in mathematics whenever one studies symmetries of a mathematical object. When these groups and semigroups are well described, certain algorithmic techniques my be used to study them. There are applications of these studies to a number of areas including computer science.

MEAKIN（9970471）和SAPIR（9978802）该提案是内布拉斯加大学林肯分校和范德比尔特大学研究人员之间的合作提案。 PI将考虑与群和半群的表示相关的几个算法问题。 特别是，他们将使用最近的结果Higman型嵌入自由伯恩赛德群到Higman提出的群体，以建立一个无限扭转群与有限数量的发电机和有限数量的关系。 他们还将使用这些嵌入结果通过代数方法研究计算复杂性。 在第二组问题中，他们将研究自由群的剩余有限扩展之间的联系，以及它们与p-adic数上多项式映射动态之间的联系。 第三组问题涉及使用自动机理论的方法来研究算法问题的子群的各种类和相关的问题。 第四组问题是关于图群的研究-群是自然出现的与半群表示有关的群。群和半群是代数对象，在数学中，每当人们研究一个数学对象的对称性时，它们就无处不在。 当这些群和半群被很好地描述时，某些算法技术可以用来研究它们。 这些研究在包括计算机科学在内的许多领域都有应用。