Formal Languages and the Word Problem
Gretchen Ostheimer, Hofstra University
Saturday May 20, 11.30-12.15, Groups in Galway 2006
Associated with every finitely generated group is a famous language
known as the word problem: the word problem of a finitely generated
group is the set of those words in the generators (and their inverses)
that represent the identity element of the group.
The word problem has been of interest to mathematicians since 1911 when
Dehn asked whether it is possible to decide whether a given word is in
the word problem.
The word problem is also of interest to computer scientists because it
provides a rich source of examples that can be used to clarify
relationships between various levels of the formal language hierarchy
from theoretical computer science.