I am interested in a quite compact and mathematically rigorous textbook (or textbooks) on the theory of computation. I wish to cover the following three basic topics: automata theory, computability, and computational complexity. I've already studied a nice book on the formal language theory, but there was almost nothing about how Chomsky's grammars correlate to automata and semigroups. Also, I don't like the "introductory" style of M. Sipser's "Introduction to the Theory of Computation" (basic concepts that can be described mathematically in 1-2 lines can take a lot of pages there). The first reason why I want to study computation theory is a deep understanding of what type of grammars and automata correspond to logic languages (say sententional, first and second-order logic). Also, I'm interested in finite model theory. Finally, I want to have a clear understanding of problems like P=NP.
A mathematically brief analogue of M. Sipser’s “Introduction to the Theory of Computation”
automatabook-recommendationcomputational complexitylogic
Best Answer
While I think Sipser is an excellent book, I share similar criticisms. I am partial to the following:
Savage (https://cs.brown.edu/people/jsavage/book/): This book starts with circuits and builds the equivalence to TMs. I very much like this book, and I think it sets folks up well to study circuit complexity. On its own, Circuit Complexity is very important classically (e.g., NC, P/poly), but also as building blocks to think about Quantum Computing. The standard model of computation in Quantum is the Quantum Circuit Model. Practice thinking about circuits is helpful in transitioning to Quantum.
Algebraic Automata Theory (https://www.cambridge.org/core/books/algebraic-automata-theory/09F9F4EC17BF48630DC21EFA2DB3EB7C)
For connections to Logic, you may be interested in Descriptive Complexity. Immerman (https://link.springer.com/book/10.1007/978-1-4612-0539-5) and Grohe (https://www.cambridge.org/core/books/descriptive-complexity-canonisation-and-definable-graph-structure-theory/BC758F6004BD96F6995D5F1EF1E29BAD) are standard references.
I am less partial to Arora--Barak. The service the book does is (in my opinion) organizational. It does a good job of pointing out what topics exist and some basic keywords to search for them. There are errors in the proofs, and they leave far too many details as exercises. It's not a good way to learn complexity if you don't know complexity. Goldreich is a better reference (https://www.wisdom.weizmann.ac.il/~oded/cc-book.html). These notes (https://michaellevet.github.io/Computational_Complexity_Notes.pdf) may also be helpful.