Graph structure and monadic second-order logic,

    a language-theoretic approach


                    Bruno Courcelle  and Joost  Engelfriet

 

               BrunoJoost

courcell@labri.fr ;  engelfri@liacs.nl

               

728 pages, 9 chapters, preface by Maurice Nivat, published by   Cambridge University Press, UK,  June  2012 :

            http://www.cambridge.org/fr/knowledge/isbn/item5758776/

For a 20% discount, see :

http://www.cambridge.org/knowledge/discountpromotion?code=Courcelle20

 

        To read Chapter 1, Overview, authors’ version.

   

Updates

       Page 555: The answer to Question 7.43 is positive. 

	A set R-structures L satisfies the semi-linearity property, if, for every CMS formula f(X1,…,Xk), the set of k-tuples of cardinalities of the components of the tuples (X1,…,Xk) that satisfy f in some structure of L is semi-linear. 
Then, the image of such a set under a CMS-transduction satisfies also the semi-linearity  property. This is an easy consequence of Theorem 7.10 (the Backwards Translation Theorem) and the observation that, if in a in a semi-linear subset of Nk, we replace  each tuple (n1, n2, ...., nk) by  (n1 + n2, ...., nk) by we get a semi-linear subset of Nk-1.

 

 Errata

               Page 468, Table 6.11. The transitions of the form adda,b[(2,{A,A'},B)] --> q  are incorrect. The correction is here.


          

               Page 710, replace reference [Wey] used on pages 423 and 686 by :

 

               K. Reinhardt: The Complexity of Translating Logic to Finite Automata, in  Automata, Logics, and Infinite Games LNCS 2500 (2002) 231-238.


Page updated 5 : September 2014.