Computer Science Research Seminar

Wednesday, October 26th, 2005

Gretchen Ostheimer
Computer Science Department
Hofstra University

Title: Group Theory and Formal Languages

Abstract:

The so-called ``word problem'' is perhaps the most basic and important of the decision problems in group theory. This problem was first considered by Max Dehn in 1911. It was proved to be undecidable in the 1950's, but in many important cases the problem is known to decidable. In this talk I will investigate how formal language theory can help us understand this fundamental problem. I will give a survey of past results in this area, discuss some brand new results (joint with Sean Cleary and Murray Elder) and suggest several interesting open problems.

NOTE: This talk is accessible to anyone with some prior exposure to automata theory. No group theory will be assumed. All students are encouraged to attend.

BACK