Logic in Computer Science (LICS 1990)

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

Authors: Courcelle, B.

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 = 	 {Courcelle, B.},
    title = 	 {On the expression of monadic second-order graph properties without quantifications over sets of edges },
    booktitle =  {Proceedings of the Fifth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1990},
    year =	 1990,
    editor =	 {John Mitchell},
    month =	 {June}, 
    pages =      {190--196},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }