Graph structure and monadic second-order logic,

    a language-theoretic approach

                    Bruno Courcelle  and Joost  Engelfriet


               BrunoJoost ;


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


For a 20% discount, see :


        To read Chapter 1, Overview, authors’ version.



       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.



               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.