Mathematical Sciences: Algorithmic Problems in Groups and Semigroups

数学科学：群和半群的算法问题

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

9623284 Meakin This grant supports the research of Professors Meakin, Margolis, Sapir and Birget to work on a series of problems in the algorithmic and computational theory of groups and semigroups. The first area is the relationship between Dehn functions of groups and semigroups and the computational complexity of the associated word problem. The next goal is to study further the properties of diagram groups associated with semigroup presentations. The third area is that of rewriting systems for various classes of groups and semigroups. The fourth area is extension problems for automata. The final area is the study of various algorithmic problems in the theory of group varieties. This is research in the field of group and semigroup theory. These areas can be thought of as the study of symmetry in the abstract. As such, this area has direct applications to many areas of physics and chemistry. Moreover, within the last 30 years, many connections to problems in data transmission have been solved using techniques from group theory. There are also direct connections to the error correcting codes that are vital for modern computing such as working with CD-ROM's as well as to theoretical computer science in general.

9623284 Meakin该补助金支持教授Meakin，Margolis，Sapir和Birget的研究，以解决一系列群体和半群的算法和计算理论问题。 第一个领域是群和半群的Dehn函数与关联字问题的计算复杂性之间的关系。下一个目标是进一步研究与半群表示相关的图群的性质。 第三个领域是重写系统的各类群体和半群。 第四个领域是自动机的扩展问题。 最后一个领域是研究群体多样性理论中的各种算法问题。 这是群和半群理论领域的研究。 这些领域可以被认为是对抽象对称性的研究。 因此，这一领域直接应用于物理和化学的许多领域。 此外，在过去的30年里，许多与数据传输问题有关的问题已经用群论的技术解决了。 也有直接联系的纠错码是至关重要的现代计算，如与光盘的工作，以及理论计算机科学的一般。