Department of Computer Science
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.