Groups, Languages and Automata

The authors focus on the interplay between groups and automata.

The groups \(G\) considered here are finitely generated, meaning that there is a finite nonempty subset \(X\) of \(G\) with the property that every element of the group can be expressed as a finite product of integer powers of elements of \(X\) and their inverses. The set \(X\) is called a generating set for the group, and the union of \(X\) and the set of the inverses of its elements is called the alphabet, denoted \(A\). Any such product is called a word, and the empty word corresponds to the group identity. The groups are often expressed by also giving a set of words that allow us to compute all possible products of group elements. These words are called defining relators, and the set of all such defining relators is denoted by \(R\). Sometimes, we are given an equation in the words in which the right hand side is the group identity. In this instance , the words are called relations When a group is described by means of generators and relators , we say that a presentation for the group is given and express this by writing \(G=\langle X;R\rangle\). If both sets are finite, the presentation is said to be finite, and \(G\) is finitely presented.

There can be no doubt that the paper by Dyck (1882) contains a decisive step in the definition of a group through a presentation. The method of describing a group in this way, leads to an area of group theory known as Combinatorial Group Theory, essentially, the study of groups through generators and relations.

In two fundamental papers by Max Dehn, in 1911 and 1912, he posed three fundamental problems for groups given by generators and relations, which he named the Word Problem, the Conjugacy Problem and the Isomorphism Problem. These problems are as follows: Assume \(G=\langle X;,R\rangle\).

The Word Problem: Given an arbitrary word \(W\) of \(G\) decide in a finite number of steps whether or not W defines the group identity.

The Conjugacy Problem: Given two words \(W\) and \(V\) of \(G\) decide in a finite number of steps whether or not the words are conjugates of each other.

The Isomorphism Problem: Given a group \(H\) with a different presentation, decide in a finite number of steps whether or not \(G\) and \(H\) are isomorphic.

An excellent description of these problems and of Combinatorial Group Theory can be found in the book Combinatorial Group Theory: Presentation of Groups in Terms of Generators and Relations by Magnus, Karrass and Solitar. The important point to note with each of these problems is that a solution if it exists can be found in a finite number of steps, indicating the algorithmic nature of Combinatorial Group Theory. The authors of the book under review focus on the Word Problem.

We assume we have a finite group \(G= \langle X;,R\rangle\), with alphabet \(A\). We denote the set of all words from \(A\) including the empty word by \(A^*\). A subset of \(A^*\) is called a language over \(A\). This is the setting for the theory of automata, which are formal processes for reading and transforming words from a language. The authors study how automata can be used to determine whether a group has a solvable word problem or not. They give detailed explanations on how automata can be used in group theory to encode complexity, to represent certain aspects of the underlying geometry of a space on which a group acts, its relation to hyperbolic groups.

Some years ago Olga Taussky Todd wrote an article for the American Mathematical Monthly titled “Why I Became a Torchbearer for Matrices”, describing how her interests in matrix theory developed, and why it is a rich area if research. In many ways, this text, though difficult, plays a similar role: it will convince the reader of the beauty and richness of Group Theory.

Charles Traina is Professor of Mathematics & Computer Science at St. John’s University, Jamaica, N.Y.