Monday, July 06, 2009

The Strangest Book on the Theory of Computation

Based on the description of the book in the World Scientific Press catalogue, I asked my university library to order a book entitled Automata Theory by Matthew Simon. I did so because it seemed to cover many topics not available elsewhere. I now regret my decision, although looking at the book did provide some amusement value. It is weird.

The first thing that a reader notices is each chapter begins with lengthy quotations about the history of slavery. No, I am not kidding. Chapter 1, for example, begins as follows:



White and Negro produces mulatto
Half white, half black

White and mulatto produces quadroon
Three-quarters white and one-quarter Negro...

etc. This strange choice is explained by the author as follows: "While this book focuses upon language, a reminder of the relationship between language, social being, responsibility, and historical context will start each chapter."

The typesetting and notation are really awful. For example, the author uses the capital letter "X" to represent ×, the cross product symbol. Terms are used without being defined: for example, "semi-automata" is used on page 7 but has not been defined. Some material is simply repeated; for example, both pages 9 and 11 contain a definition of semigroups (which are sometimes written "semi-groups"). The author frequently uses notation and abbreviations that are unique to him, such as "NDFSA" for what everyone else calls "NFA", etc.

Most of the book consists of pages and pages and pages of examples, with little explanation of what the examples are intended to illustrate. When theorems are stated, they often miss the point. For example, the pumping lemma for regular languages is stated as follows: "If an FSA has n+1 states and accepts a string ω where ω = a0 a1 ... an+1, thus |ω| = n+2, then the FSA accepts an infinite number of strings." But this is not the pumping lemma, which is a statement about languages, not automata.

This is, without a doubt, the strangest book I have every read on the theory of computation. I honestly don't know how this book ever got published.

There is also an interesting positive review of the book on Amazon:

Automata Theory by Matthew Simon is an unusually welcome book. The many examples shown include subjects not often covered, such as: the Chomsky-Schutzenberger Theorem, Kuroda Normal Forms, Ginsberg-Griebach Theorem, Simple Pushdown Automata, Syntactic Pattern Recognition, and Shape Grammers. The use of a consistent and standard notation throughout the book is also welcome, as many different subjects are discussed. The focus of the first chapter is upon Semigroups and Automata Theory(including wreath products), from a more elementary, less abstract, less mathematical viewpoint than that found in the dozen or so books covering this subject. Thus examples from automata theory are emphasized. While departures from the notation of Clifford and Preston do take place, the notation is as close as one can come to being standard, as no standard notation currently exists. Each chapter starts with a commentary or quotes relating to subjects that arise in socially oriented linguistics and automata theory. Such commentary is often omitted in books covering automata theory but is of interest to people studying Anthropological Linguistics, General (historical)Linguistics, Philosophical Linguistics, and other academic areas dealing with linguistics, but often neglected by the engineering, Computer Science and Mathematics communities.

I leave it up to the reader to try to figure out who might have written this review.


Anonymous said...

And I feel like I need a good editor...

Digressively, are there any books you would recommend for a linguist interested in computability, automata, and the like? I've read Partee et al 's Mathematical Methods and a smattering of stuff on NLP and am looking for the next step.

Jeffrey Shallit said...

Well, Hopcroft and Ullman's book Introduction to Automata, Languages, and Computation is good. It's out of print but you can easily find a used copy. I would avoid the new edition, written with Motwani.

Also, Sipser's book Introduction to the Theory of Computation is good.

student said...

are you going to be teaching cs 365 in winter 2010? if not, will you be teaching cs 365 in any near future?

Jeffrey Shallit said...


I am going to be away on sabbatical from September 2009 to September 2010. I don't know what courses I will teach in September 2010 - they haven't been assigned yet.

Anonymous said...

you could have viewed few pages of this book from google books.

toc mca said...

Nice Content about Theory of Computation.
If any one want to know about Theory of Computations, visit
Theory of Computation

hope said...

> I would avoid the new edition, written with Motwani

I read "Hopcroft and Ullman" and immediately remembered how I didnt like the book....

it seems I read the successor...