Formal languages and the word problem for groups

Rick Thomas

(University of Leicester)

If we have a generating set X for a group G, then every word in the symbols X represents an element of G. The word problem for G is defined to be the set of all words that represent the identity element. If we can decide whether or not a word is in the word problem, then we can decide whether or not two words represent the same element of G.

In this talk, we will be interested in the following question: if the word problem is known to lie in a certain class C of languages (such as the class of regular languages), what can we say about the group? On the face of it, the question does not appear to be well posed, in that the word problem with respect to one generating set might lie in C while the word problem with respect to another might not, but we find that, under fairly mild assumptions on C, this cannot happen.

The talk will survey some of what is known in this area, in particular mentioning some work on groups where the word problem is a "one-counter" language. Some familiarity with the rudiments of formal language theory will be useful (such as the meanings of the words regular, context free, recursive, ...), but very little beyond the definition of a group is required from group theory.
Tuesday 24th January 1995, 14:30
Seminar Room 322
Department of Computer Science