Finite state automata in group theory

Sarah Rees

(University of Newcastle upon Tyne)

The talk will be an introduction to the theory of automatic groups.

An automatic group is a group with certain finiteness properties which allow it to be described by finite state automata. Automatic groups arise naturally out of many mathematical questions in geometry and topology. Often they are groups of isometries of negatively curved (hyperbolic) space. The automata associated with automatic groups allow calculations to be done which would normally be infeasible.

The construction and manipulation of the finite state automata associated with an automatic group depend on various techniques from computer science, such as the Knuth Bendix rewriting procedure and algorithms to manipulate finite state automata. Other interesting classes of groups can be associated with more complex classes of machines than FSAs.
Tuesday 25th October 1994, 14:30
Seminar Room 322
Department of Computer Science