Foundations of Computation

Reviewed by Robert Marceau, Assistant Teaching Professor, University of Massachusetts Lowell on 6/9/20

Comprehensiveness rating: 4 see less

A good amount of space dedicated to mathematical background. The book covers all topics with an appropriate depth for an undergrad. Additional exercises concerning FSAs, DFAs and PDAs would be welcome. A discussion of linear bounded automatons would also be welcome.

Content Accuracy rating: 5

No errors detected

Relevance/Longevity rating: 5

Content is update, but there haven't been any recent developments for this topic.

Clarity rating: 5

Writing is clear and concise. The informal restatements are helpful for the students to grasp the topic.

Consistency rating: 5

Notation is standard and consistent.

Modularity rating: 5

The first part could serve as a brief review on discrete math.

Organization/Structure/Flow rating: 4

Although the mathematical background is useful, more space could be dedicated to FSAs, DFAs, and TMs.

Interface rating: 4

Links within the pdf would be helpful. I read in another review that the Latex source was available. This is a big plus.

Grammatical Errors rating: 5

No grammatical issues.

Cultural Relevance rating: 5

Reference to Santa, but that is fine.

Comments

Overall, a good text. Could use a bit more in the second half (DFA/FSA/TM) and computability. I would also like to see reducibility and undecidable languages discussed.

Reviewed by Brian Howard, Associate Professor of Computer Science, DePauw University on 10/15/19

Comprehensiveness rating: 4 see less

The text is fairly comprehensive, although it is probably impossible to include all of the material on these topics that any given course (other than the authors', I assume) might need. Here are the areas where I have had to supplement the text:
* Section 1.3 on Logic Circuits does not cover NAND/NOR gates, Karnaugh maps, gate delays, or common circuits such as adders and multiplexers. It only hints at sequential logic, and does not return to the topic in Chapter 3 when talking about finite-state automata.
* Section 1.5 talks about Deduction, but does not include a complete set of rules (it says "There are many other rules. Here are a few that might prove useful."); it would have been easy here to include a full set of natural deduction (introduction and elimination) rules, at least for propositional logic.
* Section 1.8 on Induction is only about induction on the natural numbers, and even when the examples of recursion in Section 1.9 (in Java) include binary trees the induction is performed "on the number of nodes", rather than introducing the (much clearer, in my opinion) notion of structural induction. I also take the opportunity to use a language such as Scala or Haskell in which recursion is more natural (and I continue to use this language in Section 2.5 when talking about programming with first-class functions). Similarly, the recursive definitions in Section 1.10 are only over the natural numbers.
* Section 3.3 on Regular Expressions briefly mentions character classes, but does not address how to deal in a practical way with Unicode character classes (which should not just be treated as the "or" of all characters in the class).
* Section 4.3 works with parse trees, but it does not go on to talk about abstract syntax trees, which I find to be a good connection between parsing and recursive functions (such as a simple interpreter) on trees.

Content Accuracy rating: 5

I have not found any errors (except I prefer to use the term "combinational logic" instead of "combinatorial logic", which I believe is a common mistake).

Relevance/Longevity rating: 4

Apart from the comments above about the somewhat dated use of Java (and later C++) for programming examples where a more modern functional language (or even the recent functional additions to Java and C++) would be more appropriate, there is very little in this text that will go out of date any time soon.

Clarity rating: 5

I started using this text precisely because Critchlow and Eck provide clearer coverage of these topics than any of the other (free) books I have tried, and certainly clearer than what I have been able to produce on my own.

Consistency rating: 5

The only complaint I have about consistency relates to the point made earlier about not introducing structural induction, and yet in Chapter 3 there is at least one proof (about converting regular expressions to finite-state automata) that uses structural induction!

Modularity rating: 5

So far, I have found it reasonably easy to merge sections of this text with my own supplemental materials. I was able to take several sections out of Chapters 1 and 2, rearrange them, and add in material (particularly on logic circuits and functional programming) to meet my needs fairly well.

Organization/Structure/Flow rating: 5

The organization is fairly standard for these topics.

Interface rating: 4

The PDF available to download does not have internal links (from the table of contents or the index). However, the LaTeX source files are available and it is easy to generate a new version in which these links are present.

Grammatical Errors rating: 5

I have not seen any issues with the grammar.

Cultural Relevance rating: 5

There is very little in this book to which this even applies -- most examples are about mathematical rather than cultural objects.

Comments

I am enjoying using the Critchlow and Eck book with my classes. Although it does not cover as much as the (now 25-year-old) Aho & Ullman text that I used to use, I am pleased with its accessibility, as well as the ease with which I have been able to rearrange and supplement it.

Reviewed by Jody Paul, Professor of Computer Science, Metropolitan State University of Denver on 4/12/19

Comprehensiveness rating: 2 see less

The particular mix of curricular topics is somewhat unconventional. The content choices reduce the potential utility of this book for existing courses (e.g., discrete math, theory of computation).
However, this particular design may serve as a model for those considering curriculum redesign.
In addition, selected content may serve well to supplement other, more comprehensive, textbooks.

Content Accuracy rating: 5

No errors detected.

Relevance/Longevity rating: 4

The content area addressed is one of the more stable within computer science. Examples given in a specific programming language (Java) and references to particular language definitions (C++) appear to be relatively easy to modify/replace in future versions. The section of applications to databases using SQL may need greater reworking.

Clarity rating: 3

The text is well-written but may pose some difficulty for the intended audience: "It has no prerequisites other than a general familiarity with computer programming." There are some oddities in language usage, for example referring to a wire "as being on and off", that can be useful simplifications or can cause unnecessary confusion depending on the specific background of the reader.

Consistency rating: 4

Tone is largely consistent.

Modularity rating: 3

Chapters and Sections are . The material is (necessarily) self-referential such that reordering of the sections would not be viable.
The content may serve well as a supplement other textbooks.

Organization/Structure/Flow rating: 4

The internal organization is consistent with the perceived intended presentation.

Interface rating: 3

Text and images appear crisp and clear.
There are no internal links within the PDF (such as for the Table of Contents or Index) so navigation is linear.
Accessibility issues (such as those articulated at Section508.gov) do not appear to have been taken into account.

Grammatical Errors rating: 5

No errors identified.

Cultural Relevance rating: 5

The text has little cultural relevance (minor historical references) and no intentionally insensitive, biased, or offensive content observed.

Comments

Instructors may find value in extracting and using parts of this work to supplement other materials and textbooks.
The PDF has some issues with accessibility. For example, a text-to-speech reader skipped multiple phrases within sentences, did not handle footnote text properly, and did not address tables, mathematical notation, or diagrams.
Readers would benefit from a greater number of worked-through examples.

Reviewed by Sherry Yang, Professor, Software Engineering Technology, Oregon Institute of Technology on 6/19/18

Comprehensiveness rating: 4 see less

This is a good introductory book. In terms of coverage, I would like to see less logic and discrete math. A shorter review of logic, sets, functions and relations would be appropriate for a computational theory class. Normally discrete math and logic are covered in other classes. As far as the coverage of languages, grammars and automata, the book hits highlights in each topic. I would like to see more in-depth discussions on topics, such as different grammatical formats, Chomosky hierarchy, decidability, variations on the turing machine, etc.

Content Accuracy rating: 5

The content appear to be technically accurate.

Relevance/Longevity rating: 5

This is a good introduction of computer theory, aka computational theory, grammars, formal languages, etc. While this subject is well-understood since the 60's, it is definitely still relevant to computing and software development today. This is usually the course before compilers. As long as we are still programming with textual language, this topic is still very relevant.

Clarity rating: 4

The writing is pretty clear. I think maybe the formatting is making it a little harder to read. The book feels very compact and concise with a lot of materials packed in.

Consistency rating: 5

Consistency is good.

Modularity rating: 5

The chapter and section divisions are good.

Organization/Structure/Flow rating: 5

The organization and structure flow is good too. I would like to see more examples but overall it is good.

Interface rating: 5

No interface issues. I would like to see more graphics/illustrations though.

Grammatical Errors rating: 5

No issues.

Cultural Relevance rating: 5

Not applicable in this case.

Comments

This is a good introductory book. I would need to supplement it with additional materials however for a semester or quarter long course. I don't normally cover logic and discrete math in such detail (over half of the book). We have separate classes for Discrete Math and Logic.

Reviewed by Nathanael DePano, Associate Professor, University of New Orleans on 2/15/17

Comprehensiveness rating: 5 see less

The text covers all areas and ideas of the subject appropriately, missing only the last portion of the NP problem that is discussed in my class (CSCI 3102: Introduction to the Theory of Computation).
Beginning chapters are very thorough; re-explaining neatly the basic technical words that will be coming in latter chapters.
It has some Python programming code in it, so that is a plus. But it has fewer diagrams and problems about PDAs, NFAs, and DFAs than the current book that we are using (Sipser).

Content Accuracy rating: 5

I did not find any inaccuracies.

Relevance/Longevity rating: 5

The text is by-and-large up-to-date. But then again, this topic is mature having been formulated and formalized in the 1930s through the 1960s.

Clarity rating: 5

The writing is easy and clear. The author uses second person perspective to explain things which makes the book interactive.

Consistency rating: 5

It is quite good.

Modularity rating: 5

The book is, in fact, easy to subdivide into smaller modules. It will be easy to re-organize the course content if and when time becomes an issue (common around here because of the threat of hurricanes during the storm season).

Organization/Structure/Flow rating: 4

Topics are presented in a suitable manner. However, FSAs are introduced a tad too late for my taste. And, as mentioned before, there are only a limited number of PDA, FSA, NFA problems.

Interface rating: 5

No noticeable interface issues were encountered.

Grammatical Errors rating: 5

No grammatical errors were found.

Cultural Relevance rating: 5

As a textbook about the Theory of Computation, this criterion is marginally relevant. That being said, there were no obvious references to race, ethnicity, or background.

Comments

I am happy that this book is available on an "open" basis. At the very least, this book could serve as a good reference and balancing tool for students enrolled in my CSCI 3102 classes. I am willing to even adopt it as a primary textbook after this Spring 2017 semester where I have already made arrangements to use Sipser for the course.