Collaborative Research: Algorithmic Problems in Groups and Semigroups

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

ABSTRACT, MEAKIN(9970471) and SAPIR 999788020This 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.