Codes and Automata

The word “code” means different things to different people, even within mathematics. There are several different definitions of “code” that one comes across.

In the introduction to their 1985 book Theory of Codes, Jean Berstel and Dominique Perrin write that the study of codes is “`the study of the properties concerning factorizations of words into a sequence of words taken from a given set." Like most areas of mathematics, this problem can be looked at in many different ways — depending on your point of view you may choose to use results from graph theory, theoretical computer science, topology, or many other areas of mathematics to look at codes. Berstel and Perrin primarily choose to view a code as an embedding of one free monoid into another, allowing them to use algebraic techniques to study properties of variable length codes.

More than two decades after Theory of Codes was released, the authors, along with Christophe Reutenauer, have completely reworked their book, and released Codes and Automata as an entry in Cambridge University Press’s “Encyclopedia of Mathematics” series. As the title suggests, the book is about codes, automata, and the relationships between them. The authors describe techniques of constructing codes with various nice properties and show how to use automata to realize these codes. The authors treat both theoretical and algorithmic aspects of the subjects, and the book is littered with explicit examples as well.

The resulting book is extensive and at times quite deep, but the authors manage to keep it quite accessible, as they introduce most topics at an elementary level and explain in detail before exploring all of the connections with different areas of mathematics. The opening chapter of the book is extremely elementary, setting notation and giving definitions along with a quick tour through many of the areas of mathematics that they will call on in the later chapters. The next seven chapters of the book concern what the authors call “direct methods”, which primarily involve looking at the combinatorics on words and an analysis of the factoring of elements of a free monoid. Special attention is given to prefix codes (in which no element of our code is a prefix of another word) and bifix codes (in which no element of our code is either a prefix or a suffix of another word). These codes are particularly useful in real life applications, as they allow for easier decoding algorithms.

The authors introduce a different set of methods in the ninth chapter, which they refer to as “syntatic methods”. In general, these involve looking at the monoid of relations associated to a given automaton, and considering computations related to these monoids rather than on the original elements. This approach allows the authors to prove different types of results over the remainder of the book, including the so-called “Road Coloring Problem” which shows that, under certain technical conditions, a synchronizing coloring of a graph will exist. Another chapter deals factorizations of cyclic groups and the way that these factorizations can lead to the construction of maximal codes.

Throughout this book, the authors use ideas from a wide range of mathematics. Probability spaces are involved, as are semisimple algebras and symbolic dynamics. Results from combinatorics and group theory are ubiquitous. But despite all of the machinery the authors bring in, they do an excellent job of keeping the exposition clear. Most chapters contain sets of exercises, many of which have solutions in the back of the book, and each chapter ends with a section of historical and biographical notes. For all of these reasons, this book will serve as an excellent introduction for any reader interested in learning about codes from the viewpoint of Berstel, Perrin and Reutenauer.

Darren Glass is an Associate Professor of Mathematics at Gettysburg College whose research interests include algebraic geometry, Galois theory, and cryptography. He can be reached at dglass@gettysburg.edu.