views:

904

answers:

6

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.

+1  A: 

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.

David Johnstone
Spiser’s is a very nice book in Automata Theory, Languages, and Computation but it’s very basic and don’t treat formal logic.My title is a bit misleading. It’s just there a relation between monadic second order logic and Büchi Automata.
anno
I myself found that book a bit confusing - examples were too 'perfect' and figures/examples were not explained as well as I would have liked. imho!
rascher
A: 

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.

spiffyman
I know Speech and Language Processing and that’s not what I’m looking for :) But I’ll take a look at the Blackburn book.
anno
A: 

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.

Jørgen Fogh
I’ve found the TOC (http://www.ulb.tu-darmstadt.de/tocs/19825007X.pdf), the books looks interesting in its own right but I’m afraid that the "Model Checking" bias is not what I’m looking for. What level of mathematical maturity is required to skim through it ?
anno
+2  A: 
eed3si9n
The books looks interesting but the lecture format and the numerous (unrelated) subjects presented and the scarcity of the presentation of S1S make it not a very good solution.
anno
Languages, Automata and Logic by Wolfgang Thomas is the best presentation I've found for now.
anno
A: 

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.

Shai Berger
+1  A: 

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,

anno