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} }