Advanced Formal logic / Automata Theory textbook

Question

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.

Answer 1

So this is the best curriculum I can come with :

For Beginners in Logic :

Peter J. Cameron, Sets, Logic and Categories, Springer, Springer Undergraduate Mathematics Series, 1999, URL.

James L. Hein, Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers, 2009 (3th ed) URL.

Logic for the computer scientist.

For Beginners in Automata and Formal Langugage :

Michael Sipser, Introduction to the Theory of Computation, Course Technology, 2005 (2nd), URL.

and

Alan P. Parkes, Introduction to Languages, Machines, and Logic, Springer, 2002.

and

Peter Linz, An introduction to formal languages and automata, Jones & Bartlett Publishers, 2000 (3 ed) URL.

and

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley , 1979, (1st ed), ISBN : 0-201-02988-X; URL.

Intermediate level Logic (undergraduate):

D. Ebbinghaus , Mathematical Logic, Springer, URL.

or

Elliott Mendelson, Introduction to Mathematical Logic, URL

Advanced level (Graduate):

Wolfgang Thomas, Languages, Automata and Logic, 1996.

Leoni Libkin, Elements of Finite Model Theory, Springer, 2004, URL, TOC.

For Research

Benedikt Bolli, Formal models of communicating systems, Springer, 2006, URL.

Grädel, Erich; Thomas, Wolfgang; Wilke, Thomas (Eds.), Automata, logics, and infinite games, Springer, 2002, URL,

Answer 2

You're going to be a little surprised, but I think the book you're looking for is Foundations of Databases by Abiteboul, Hull and Vianu (also known as the "Alice book", because Alice is painted on its cover and stars in chapter-introduction dialogs with the authors). It's not a book about SQL, but about the theory of databases -- logic and its implementation in programs and functions -- so it spends quite a lot on issues of complexity and computability of query languages; and the authors make a great effort to be friendly and communicative.

Answer 3

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 http://ecx.images-amazon.com/images/I/51JKHJGWBRL._BO2,204,203,35,-76_AA240_SH20_OU01_.jpg

Answer 4

I remember reading about Büchi Automata in Principles of Model Checking, which seems like a pretty good book. Of course, the focus is on the application to model checking, but model checking is mostly logic anyway.

Answer 5

This may not be quite what you're looking for, but I learned a great deal from Blackburn et al's Modal Logic, and I learned what I know of automata from Jurafsky and Martin's Speech and Language Processing, esp. Chapter 2. If nothing else, both provide excellent groundwork for further research.

Answer 6

I've heard good things about Michael Sipser's Introduction to the Theory of Computation. I actually have it right in front of me, although I haven't started reading it yet.