0
$\begingroup$

What are some good books and surveys for learning about first-order logic and monadic second-order logic?

I'm a graduate student in computer science with a focus on algorithms. For model-checking on graphs, I need to be familiar with the FO and MSO logics.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

It depends what precisely do you want to learn. A good reference is the finite model theory book by Libkin. https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf (chapters 2 and 7).

If you want more specific references, please be more precise with your question.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. First, I would like to become familiar with the definitions and theorems of FO and MSO, although not on an advanced level. Furthermore, I am interested in knowing what problems and properties in graph theory are expressed and cannot be expressed by FO and MSO. $\endgroup$
    – fva
    Commented Jan 5, 2023 at 12:37
  • $\begingroup$ Ok, so I think that the first two chapters would be ok of Libkin's book will be ok (+ the chapter about MSO). Otherwise, you can also go through the following undergrad book: Mathematical Logic, 2nd Edition (Undergraduate Texts in Mathematics) amazon.com/Mathematical-Logic-Undergraduate-Texts-Mathematics/… $\endgroup$
    – Bartosz Bednarczyk
    Commented Jan 5, 2023 at 14:01
  • $\begingroup$ Thanks! It seems like a great book. The book "Graph Structure and Monadic Second-Orderer Logic" by Courcelle and Engelfriet was also recommended by a friend. $\endgroup$
    – fva
    Commented Jan 6, 2023 at 16:10
  • $\begingroup$ Yes, but this is a way more advanced than the ones that I told you (say, undergrad level vs PHD student / researcher level). $\endgroup$
    – Bartosz Bednarczyk
    Commented Jan 6, 2023 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.