Department of Computer Science

Home | Introduction | Programs | Courses | People | Colloquia | Feedback

**Title**: Algorithms For Studying Infinite Groups

**Speaker**: Dr. Gretchen Ostheimer

**Date/Time**: November 1, 2000

**Location**: Adams 204

**Abstract**: Infinite groups provide a rich
context in which to explore the interactions between math and computer science
since such groups arise in the study of formal languages, rewriting systems,
decidability and algorithms. I will discuss a classical problem concerning infinite
groups -- the conjugacy problem as posed by Dehn in 1911 -- and its connection
to decidability and algorithms. In joint work with Bettina Eick from the University
of Kassel, Germany, we are developing a practical algorithm for solving this
problem given certain restrictions concerning the input. (By "practical algorithm"
we mean an algorithm that is fast enough to handle interesting examples in a
reasonable amount of time using current computer technology.) In this talk I
will attempt to give an overview of why we are interested in this problem, the
challenges that are inherent in solving it, the progress we have made so far,
and the difficulties that remain to be overcome.