Book Review of “Elements of Automata Theory”

During summer 2010 I started reading a book titled Elements of Automata Theory by Jacques Sakarovitch. It took me one year to read the book and submit my review to Bill Gasarch during summer 2011. It will be appearing in SIGACT book review column soon. I am posting my review here for the benefit of everybody.

———————————————————————————————————————————

Book : Elements of Automata Theory by Jacques Sakarovitch
Reviewer : Shiva Kintali

Introduction

During my undergrad I often found myself captivated by the beauty and depth of automata theory. I wanted to read one book on automata theory and say that I “know” automata theory. Couple of years later I realized that it is silly to expect such a book. The depth and breadth of automata theory cannot be covered by a single book.

My PhD thesis is heavily inspired by automata theory. I had to read several (fifty year old) papers and books related to automata theory to understand several fundamental theorems. Unfortunately, the concepts I wanted to learn are scattered in multiple books and old research papers, most of which are hard to find. When I noticed that Prof. Bill Gasarch is looking for a review of Elements of Automata Theory, I was very excited and volunteered to review it, mainly because I wanted to increase my knowledge about automata theory. Given my background in parsing technologies and research interests in space-bounded computation I wanted to read this book carefully. This book is around 750 pages long and it took me around one year to (approximately) read it. It is very close to my expectations of the one book on automata theory.

First impressions : Most of the books on automata theory start with the properties of regular languages, finite automata, pushdown automata, context-free languages, pumping lemmas, Chomsky hierarchy, decidability and conclude with NP-completeness and the P vs NP problem. This book is about “elements” of automata theory. It focuses only on finite automata over different mathematical structures. It studies pushdown automata only in the context of rational subsets in the free group. Yes, there is 750 pages worth literature studying only finite automata.

This book is aimed at people enthusiastic to know the subject rigorously and not intended as a textbook for automata theory course. It can also be used by advanced researchers as a desk reference. There is no prerequisite to follow this book, except for a reasonable mathematical maturity. It can be used as a self-study text. This book is a direct translation of its french original.

 
Summary

This book is divided into five major chapters. The first three chapters deal with the notions of rationality and recognizability. A family of languages are rationally closed if it is closed under rational operations (union, product and star). A language is reconizable if there exists a finite automata that recognizes it. The fourth and fifth chapters discuss rationality in relations. Chapter 0 acts as an appendix of several definitions of structures such as relations, monoids, semirings, matrices, graphs and concepts such as decidability. Following is a short summary of the five major chapters. There are several deep theorems (for example, Higman’s Theorem) studied in this book. I cannot list all of them here. The chapter summaries in the book have more details.

Chapter 1 essentially deals with the basic definitions and theorems required for any study of automata theory. It starts with the definitions of states, transitions, (deterministic and nondeterministic) automaton, transpose, ambiguity and basic operations such as union, cartesian product, star, quotient of a language. Rational operators, rational languages and rational expressions are defined and the relation between rationality and recognizability is established leading to the proof of Kleene’s theorem. String matching (i.e., finding a word in a text) is studied in detail as an illustrative example. Several theorems related to star height of languages are proved. A fundamental theorem stating that `the language accepted by a two-way automaton is rational’ is proved. The distinction between Moore and Mealy machines is introduced.

Chapter 2 deals with automata over the elements of an arbitrary monoid and the distinction between rational set and recognizable set in this context. This leads to a better understanding of Kleene’s theorem. The notion of morphism of automata is introduced and several properties of morphisms and factorisations are presented. Conway’s construction of universally minimal automaton is explained and the importance of well quasi-orderings is explained in detail. Based on these established concepts, McNaughton’s theorem (which states that the star height of a rational group language is computable) is studied with a new perspective.

Chapter 3 formalizes the notion of “weighted” automata that count the number of computations that make an element be accepted by an automaton, thus generalizing the previously introduced concepts in a new dimension. Languages are generalized to formal series and actions are generalized to representations. The concepts and theorems in this chapter makes the reader appreciate the deep connections of automata theory with several branches of mathematics. I personally enjoyed reading this chapter more than any other chapter in this book.

Chapter 4 builds an understanding of the relations realized by different finite automata in the order they are presented in chapters 1, 2 and 3. The Evaluation Theorem and the Composition Theorem play a central role in understanding this study. The decidability of the equivalence of transducers (with and without weigths) is studied. This chapter concludes with the study of deterministic and synchronous relations.

Chapter 5 studies the functions realized by finite automata. Deciding functionality, sequential functions, uniformisation of rational relations by rational functions, semi-monomial matrix representation, translations of a function and uniformly bounded functions are studied.

There are exercises (with solutions) at the end of every section of every chapter. These exercises are very carefully designed and aid towards better understanding of the corresponding concepts. First time readers are highly encouraged to solve (or at least glance through) these exercises. Every section ends with Notes and References mentioning the corresponding references and a brief historical summary of the chapter.

 
Opinion

Overall I found the book very enlightening. It has provided me new perspectives on several theorems that I assumed I understood completely. Most of the concepts in this book are new to me and I had no problems following the concepts and the corresponding theorems. The related exercises made these topics even more fun to learn. It was a joy for me to read this book and I recommend this book for anyone who is interested in automata theory (or more generally complexity theory) and wants to know the fundamental theorems of theory of computing. If you are a complexity theorist, it is worthwhile to look back at the foundations of theory of computing to better appreciate its beauty and history. This book is definitely unique in its approach and the topics chosen. Most of the topics covered are either available in very old papers or not accesible at all. I applaud the author for compiling these topics into a wonderful free-flowing text.

This book is nicely balanced between discussions of concepts and formal proofs. The writing is clear and the topics are organized very well from the most specific to the most general, making it a free-flowing text. On the other hand, it is very dense and requires lots of motivation and patience to read and understand the theorems. The author chose a rigorous way of explaining rationality and recognizability. Sometimes you might end up spending couple of hours to read just two pages. Such is the depth of the topics covered. Beginners might find this book too much to handle. I encourage beginners to read this book after taking an introductory automata theory course. This is definitely a very good reference text for researchers in the field of automata theory.

In terms of being used in a course, I can say that a graduate level course can be designed from a carefully chosen subset of the topics covered in this book. The exercises in the book can be readily used for such a course.

This is an expensive book, which is understandable based on the author’s efforts to cover several fundamental topics (along with exercises) in such a depth. If you think it is expensive, I would definitely suggest that you get one for your library.

———————————————————————————————————————————