Courcelle, Bruno; Engelfriet, Joost [Nivat, Maurice] Graph structure and monadic second-order logic. A language-theoretic approach. (English) Zbl 1257.68006 Encyclopedia of Mathematics and its Applications 138. Cambridge: Cambridge University Press (ISBN 978-0-521-89833-1/hbk). xiv, 728 p. (2012). From the foreword of the book written by Maurice Nivat:“The genesis of this great and beautiful book spans more than 20 years. It collects and unifies many theoretical notions and results published by Bruno Courcelle and others in a large number of articles.I believe that this book will […] quickly become a classic and provide an easy access to the burgeoning world of graph algorithms and its numerous applications throughout the sciences and beyond.”“The comments above were written two years ago, when Bruno Courcelle’s book was only 500 pages long, and I cannot change what I wrote then: it is a great and beautiful book that is going to take its place very soon on the library shelves of all the departments of computer science around the world. But now the book is 700 pages long and has two authors, Bruno and Joost Engelfriet. What happened is that Bruno sent the previous version to Joost to read and suggest corrections and improvements. […] And Joost had so many things to suggest that it is another book that I present today: thicker, with new results and a number of proofs that have been replaced by simpler and more elegant ones. Obviously the cooperation between Bruno and Joost was a very fruitful one indeed.[T]his beautiful book, which I consider to be a wonderful source of knowledge in computer science […] is a theoretical book, and for that reason some people may find it hard to read, but reading it is worth the pain, because the formalism introduced and the methods presented have already led to many new algorithms on graphs (as the number of citations of Bruno’s published papers show) and they will lead to many others in the future. To anyone interested in graph algorithms I can only recommend that they read this book first.For indeed this book lies at the very heart of computer science, which is the expressiveness of the languages used to represent and manipulate information and information structures, graphs being among the most widely used information structures. Progress in the efficiency, liability and simplicity of algorithms comes mainly from the use of better representations, better structures and a better understanding of the different ways in which one can describe sets of data and express their properties. This book provides a huge number of conceptual tools to design and study graph algorithms that no one should ignore.” Reviewer: Saeed Salehi (Tabriz) Cited in 4 ReviewsCited in 192 Documents MSC: 68-02 Research exposition (monographs, survey articles) pertaining to computer science 03B15 Higher-order logic; type theory (MSC2010) 03D05 Automata and formal grammars in connection with logical questions 05C85 Graph algorithms (graph-theoretic aspects) 05C90 Applications of graph theory 68Q45 Formal languages and automata 68R10 Graph theory (including graph drawing) in computer science Keywords:finite graphs; graph algorithms; formal languages; monadic second-order logic Software:Autowrite; MONA PDFBibTeX XMLCite \textit{B. Courcelle} and \textit{J. Engelfriet}, Graph structure and monadic second-order logic. A language-theoretic approach. Cambridge: Cambridge University Press (2012; Zbl 1257.68006)