During summer 2010 I started reading a book titled Elements of Automata Theory by Jacques Sakarovitch
———————————————————————————————————————————
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.
———————————————————————————————————————————
] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.
, there exists a logspace algorithm that, when given a graph 
of treewidth 
, decides whether the pathwidth of 
, and if so, finds a path decomposition of 
in logspace.
, how fast can we verify that 
? Recently Datta et. al [DLNTW'09] proved that the canonization of planar graph is logspace-complete. The following simple exercise shows that partial 2-trees are planar graphs. Hence the result of [DLNTW'09] implies that partial 2-trees can be canonized in logspace.
? Partial 3-trees may not be planar. An example is 
itself. The tree width of 
-free.
. LogCFL is the best known upper bound for graph isomorphism of partial k-trees [DTW'10]. One of the bottleneck, finding a tree decomposition of partial k-tree in logspace, is resolved recently [EJT'10]. The above mentioned papers make use of a decomposition of the input graph into two- or three-connected subgraphs, constructing an appropriate tree of these subgraphs, using the known structural properties of two- and three-connected graphs to canonize these subgraphs and using Lindell’s result to canonize the entire graph. Unfortunately no clean characterization exists for graphs with connectivity at least four. Many long-standing open problems in graph theory are trivial for 2- and 3- connected graphs and open for higher connectivity. A clean characterization of 4-connected graphs seems to be a major bottleneck in improving the space complexity of canonization of partial 4-trees. I am lost 
where 
-gates have fanin 2 and 
-gates are only applied to input variables. Let 
be a boolean function on 
variables and 
be a circuit computing 
. For an output gate 
, let 
and 
be the sub-circuits, whose outputs are inputs to 
be the depth of circuit 
be the minimum depth of a circuit computing 
such that 
. Consider the communication game between two players (
and 
), where 
and 
. The goal of the players to find a coordinate 
such that 
. Let 
represent the minimum number of bits they have to communicate in order for both to agree on such coordinate.
.
(resp. 
) represent the minimum number of bits that 
(resp. 
) represent the AND-depth (resp. OR-depth) of 
) + 1. AND-depth of an OR gate 
). AND-depth of a circuit 
(resp. 
) be the minimum AND-depth (resp. OR-depth) of a circuit computing 
corresponds to the AND-depth and 
corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.
be a directed graph. Let 
be the underlying undirected graph of 
be a path in 
. Let 
be an edge along the path 
is called neutral edge if both 
and 
are in 
. Edge 
and 
. Edge 
and 
.
to 
in 
to 
then there is a balanced path from 
?
) using zig-zag graph product seems to be a challenging task.
. The directed simple path from 
. There is a cycle of length 
. All the edges (except 
. It is known that 
. The following theorem states that it is unlikely that GI is NP-complete.
for graphs with 
, then GI is neither NP-complete nor in P.
and two lists of nodes 
, is there an automorphism in G mapping 
to 
for 1 ≤ i ≤ k ? Show that this problem is reducible to GI.
, 
, 
and 
.
many-one reductions. 
Turing reducible to the determinant [Cook'85]. It is known that 
and 
. Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of 
. In particular, what is the relation between 
and 
? A proof of this would imply that “if GI is NP-complete then 
“, improving the above mentioned theorem.
.
coNP is non-empty. It is easy to see that all languages in P are in NP 
NP 
NP 
is in NP 
. Did we make any progress/anti-progress towards resolving the 
is defined as follows :
table filled with entries from 
, which we interpret as the multiplication table of an 
of 
, defined as the closure of 
, a branching program in which each node can only evaluate a binary product within an 
nodes to solve all 
for any 
. 
-ary tree of height 
, whose internal nodes are labeled with ![[k] = \{1, . . . , k\}](http://s0.wp.com/latex.php?latex=%5Bk%5D+%3D+%5C%7B1%2C+.+.+.+%2C+k%5C%7D&bg=ffffff&fg=444444&s=0 "[k] = \{1, . . . , k\}")
, and whose leaves are labeled with elements of ![[k]](http://s0.wp.com/latex.php?latex=%5Bk%5D&bg=ffffff&fg=444444&s=0 "[k]")
. Each node obtains a value in 
and conjecture that 
. They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that 
