You are previewing Graph Structure and Monadic Second-Order Logic.
O'Reilly logo
Graph Structure and Monadic Second-Order Logic

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.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Dedication
  6. Contents
  7. Foreword by Maurice Nivat
  8. Introduction
  9. 1. Overview
    1. 1.1 Context-free grammars
    2. 1.2 Inductive sets of properties and recognizability
    3. 1.3 Monadic second-order logic
    4. 1.4 Two graph algebras
    5. 1.5 Fixed-parameter tractability
    6. 1.6 Decidability of monadic second-order logic
    7. 1.7 Graph transductions
    8. 1.8 Monadic second-order logic with edge set quantifications
    9. 1.9 Relational structures
    10. 1.10 References
  10. 2. Graph algebras and widths of graphs
    1. 2.1 Algebras and terms
    2. 2.2 Graphs
    3. 2.3 The HR algebra of graphs with sources
    4. 2.4 Tree-decompositions
    5. 2.5 The VR algebra of simple graphs with ports
    6. 2.6 Many-sorted graph algebras
    7. 2.7 References
  11. 3. Equational and recognizable sets in many-sorted algebras
    1. 3.1 The equational sets of an algebra
    2. 3.2 Transformations of equation systems
    3. 3.3 Intermezzo on automata
    4. 3.4 The recognizable sets of an algebra
    5. 3.5 References
  12. 4. Equational and recognizable sets of graphs
    1. 4.1 HR-equational sets of graphs
    2. 4.2 HR-recognizable sets of graphs
    3. 4.3 VR-equational sets of simple graphs
    4. 4.4 VR-recognizable sets of simple graphs
    5. 4.5 HR- and VR-equational and recognizable sets
    6. 4.6 References
  13. 5. Monadic second-order logic
    1. 5.1 Relational structures and logical languages
    2. 5.2 Graph properties expressible in monadic second-order logic
    3. 5.3 Monadic second-order logic and recognizability
    4. 5.4 Decidable monadic second-order theories
    5. 5.5 Logical characterization of recognizability
    6. 5.6 Equivalences of logical formulas
    7. 5.7 References
  14. 6. Algorithmic applications
    1. 6.1 Fixed-parameter tractable algorithms for model-checking
    2. 6.2 Decomposition and parsing algorithms
    3. 6.3 Monadic second-order formulas compiled into finite automata
    4. 6.4 Other monadic second-order problems solved with automata
    5. 6.5 References
  15. 7. Monadic second-order transductions
    1. 7.1 Definitions and basic properties
    2. 7.2 The Equationality Theorem for the VR algebra
    3. 7.3 Graph transductions using incidence graphs
    4. 7.4 The Equationality Theorem for the HR algebra
    5. 7.5 Decidability of monadic second-order satisfiability problems
    6. 7.6 Questions about logical characterizations of recognizability
    7. 7.7 References
  16. 8. Transductions of terms and words
    1. 8.1 Terminology
    2. 8.2 Tree-walking transducers
    3. 8.3 The basic characterization
    4. 8.4 From jumping to walking
    5. 8.5 From global to local tests
    6. 8.6 Multi bottom-up tree-to-word transducers
    7. 8.7 Attribute grammars and macro tree transducers
    8. 8.8 Nondeterminism
    9. 8.9 VR-equational sets of terms and words
    10. 8.10 References
  17. 9. Relational structures
    1. 9.1 Two types of ternary relational structures related to ordered sets
    2. 9.2 Relational structures of bounded tree-width
    3. 9.3 Terms denoting relational structures
    4. 9.4 Sparse relational structures
    5. 9.5 References
  18. Conclusion and open problems
  19. References
  20. Index of notation
  21. Index