2002/12/30 by Bruno Courcelle · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #semigroups and automata theory #Hypergraph #Decidability #Bounded function #Orientation (vector space) #Combinatorics #Rank (graph theory) #Spanning tree #Undirected graph #Order (exchange) #Extension (predicate logic) #Graph #Mathematics #Discrete mathematics #Computer science
paper · doi:10.1109/lics.1993.287589
openalex publication_date 2002/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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).>