Mathematical Sciences: Algorithmic Problems in Groups and Semigroups

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

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.