Department of Computer Science

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

Computer Science Colloqium

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.