Logic in Computer Science (LICS 1993)

Paper: Monadic second-order logic and hypergraph orientation (at LICS 1993)

Authors: Bruno Courcelle

Abstract

It is proved that in every undirected graph or, more generally, in every undirected hypergraph of bounded rank, one can specify an orientation of the edges or hyperedges by monadic second-order formulas using quantifications on sets of edges or hyperedges. The proof uses an extension to hypergraphs of the classical notion of a depth-first search spanning tree. Applications are given to the partially open problem of characterizing the classes of graphs (or hypergraphs) having decidable monadic theories, with and without quantifications on sets of edges (or hyperedges)

BibTeX

  @InProceedings{Courcelle-Monadicsecondorderl,
    author = 	 {Bruno Courcelle},
    title = 	 {Monadic second-order logic and hypergraph orientation},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993},
    year =	 1993,
    editor =	 {Moshe Vardi},
    month =	 {June}, 
    pages =      {179--190},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }