×

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.”

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

Software:

Autowrite; MONA
PDFBibTeX XMLCite