Mathematical Sciences: Algorithmic Problems in Groups and Semigroups

点击翻译按钮获取中文摘要

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.