5 found
Order:
  1.  13
    Monadic Second-Order Logic, Graph Coverings and Unfoldings of Transition Systems.Bruno Courcelle & Igor Walukiewicz - 1998 - Annals of Pure and Applied Logic 92 (1):35-62.
    We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  9
    The Monadic Second-Order Logic of Graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
    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 spanning tree. Applications are given to the characterization of the classes of graphs and hypergraphs having decidable monadic theories.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  3.  7
    Circle Graphs and Monadic Second-Order Logic.Bruno Courcelle - 2008 - Journal of Applied Logic 6 (3):416-442.
  4.  4
    The Monadic Second-Order Logic of Graphs XV: On a Conjecture by D. Seese.Bruno Courcelle - 2006 - Journal of Applied Logic 4 (1):79-114.
  5.  3
    Automata for the Verification of Monadic Second-Order Graph Properties.Bruno Courcelle & Irène Durand - 2012 - Journal of Applied Logic 10 (4):368-409.