Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Books
  3. Graph Structure and Monadic Second-Order Logic
  • Cited by 174
Publisher:
Cambridge University Press
Online publication date:
July 2012
Print publication year:
2012
Online ISBN:
9780511977619
DOI:
https://doi.org/10.1017/CBO9780511977619
Subjects:
Mathematics (general), Mathematics, Logic, Categories and Sets, Computer Science, Programming Languages and Applied Logic
Series:
Encyclopedia of Mathematics and its Applications (138)
Information

Book description

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The authors not only provide a thorough description of the theory, but also detail its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory.

Reviews

'In its huge breadth and depth the authors manage to provide a comprehensive study of monadic second-order logic on graphs covering almost all aspects of the theory that can be presented from a language theoretical or algebraic point of view. There is currently no other textbook or any other source that matches the range of materials covered in this book. As such it is a fantastic resource for those who to study this area [and] will undoubtedly turn into the standard reference for this area.'

Stephan Kreutzer Source: Mathematical Reviews

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents

Metrics

Altmetric attention score

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.