Formal languages and group theory

Introduction Our aim is to explore some connections between word problems of groups and formal language theory. One question is whether any finitely presented group has a recursive word problem, i.e., if there is an algorithm to decide if a given word in the generators of such a group represents the identity; this was shown not to be the case by Novikov and Boone independently [37, 6]. A finitely presented group has a recursively enumerable word problem however, i.e., there is a process listing the words representing the identity; the process will not terminate (there are infinitely many such words) but any word representing the identity will eventually appear. We are interested in relating the complexity of the word problem (as a formal language) to the algebraic structure of the group. With regards to the classes of languages we have just mentioned, there is the beautiful Higman embedding theorem [16] which says that a finitely generated group has a recursively enumerable word problem if and only if it can be embedded in a finitely presented group. For recursive languages it was shown by Boone and Higman [7] that a finitely generated group has a recursive word problem if and only if it can be embedded in a simple group which can, in turn, be embedded in a finitely presented group. This was strengthened by Thompson [44] who showed that a finitely generated group has a recursive word problem if and only if it can be embedded in a finitely generated simple group which can, in turn, be embedded in a finitely presented group. There is a natural (and seemingly difficult) question (attributed to Higman) which asks if we can strengthen this further by proving that every finitely generated group with a recursive word problem can be embedded in a finitely presented simple group. We will survey some work concerning groups whose word problem is a simpler type of language. We will concentrate on the class of context-free languages, some subclasses of the context-free languages and some other related classes (such as intersections and complements of context-free languages); there are many other interesting classes of languages we have not discussed such as the the class of real-time languages (see [18, 20, 23] for example) the class of growing context-sensitive languages (see [22, 29]) and the class of context-sensitive languages (see [31, 41]).