Paper: On the expression of monadic second-order graph properties without quantifications over sets of edges (at LICS 1990)

Authors: Bruno Courcelle

Abstract

For graphs of degree at most some fixed integer, the same properties can be expressed by monadic second-order formulas with and without quantifications over sets of edges, with and without auxiliary orientations. Similar results hold for partial k-trees for fixed k, and for graphs of tree-width at most k. These results are related to the possibility of testing graph properties in polynomial time for graphs generated by context-free graph-grammars of various types

BibTeX

  @InProceedings{Courcelle-Ontheexpressionofmo,
    author = 	 {Bruno Courcelle},
    title = 	 {On the expression of monadic second-order graph properties without quantifications over sets of edges },
    booktitle =  {Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS 1990)},
    year =	 {1990},
    month =	 {June}, 
    pages =      {190--196},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }