On context-free sets of graphs and their monadic second-order theory

  • Bruno Courcelle
Part II Technical Contributions
Part of the Lecture Notes in Computer Science book series (LNCS, volume 291)


The algebraic framework for studying graphs yields a notion of system of equations defining equational sets of graphs. Context-free graph grammars (where the rewriting step is the substitution a graph for an hyperedge) are defined. The context-free and the equational sets of graphs are the same. The monadic second-order theory of a context-free set of graphs is decidable.


Context-free graph grammar Monadic second-order logic decision problem 


  1. [28]
    J.R. BUCHI, Weak 2nd order logic and finite automata, Z. Math Logik 5(960) 66–92.Google Scholar
  2. [29]
    B. COURCELLE, A representation of graphs by algebraic expressions and its use for graph rewriting systems, this volume.Google Scholar
  3. [30]
    B. COURCELLE, An axiomatic definition of context-free rewriting and its application to NLC grammars, Report 8706, Bordeaux 1 University, 1987.Google Scholar
  4. [31]
    J.DONER, Tree acceptors and applications. Jour. Comput. System Sci. 4(70) 406–451Google Scholar
  5. [32]
    J.W. THATCHER, J.B. WRIGHT, Generalized automata theory, Maths Systems Theory 2 (1970) 57–81CrossRefGoogle Scholar
  6. [33]
    P. SEYMOUR, N. ROBERTSON, Some new results on the well quasiordering of graphs, Annals of Discrete Maths 23 (1984) 343–354.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1987

Authors and Affiliations

  • Bruno Courcelle
    • 1
  1. 1.Bordeaux I University Mathematiques et InformatiqueTalenceFrance

Personalised recommendations