Theory of Computation

Dexter C. Kozen

Mentioned 1

This textbook is uniquely written with dual purpose. It cover cores material in the foundations of computing for graduate students in computer science and also provides an introduction to some more advanced topics for those intending further study in the area. This innovative text focuses primarily on computational complexity theory: the classification of computational problems in terms of their inherent complexity. The book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises.

More on

Mentioned in questions and answers.

I know this is more a Math/Formal Language/Automata/Computer science question than an a programming one, but I hope I can get some advice on a comprehensible textbook (not an indecipherable monograph) on formal logic beyond Propositional and Predicate Calculus. I’m especially interested in monadic second order logic and Büchi Automata.

For now, I’ve only found Automata theory and its applications by Bakhadyr Khoussainov, Anil Nerode. Automata, logics, and infinite games By Erich Grädel, Thomas Wilke (eds). And Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic Benedikt Bollig....Way over my head.

You seem to have specific topic you want from a book, so I looked into the index of some books in Amazon. Although I've never read this one, Theory of Computation by Dexter C. Kozen might interest you.

Büchi automation, 155, 159, 161, 283, 298, 343
      determinization, 167-170

monadic second-order theory
    of n successors, 154
    of successor, 154-159

The covered pages are in Lecture 25 Automata on Infinite Strings and S1S, the first page is available for preview from the link.

Theory of Computation