The monadic second-order logic of graphs. VIII: Orientations

DOI10.1016/0168-0072(95)94698-VzbMath0830.03016MaRDI QIDQ1842126

Bruno Courcelle

Publication date: 30 January 1996

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logicdecidabilitydefinabilitytree-widthcomplexity measurebounded rankorientation of the edgesrepresentation of graphs and hypergraphs as logical structures

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25) Second- and higher-order model theory (03C85)

Related Items

The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Recognizability equals definability for graphs of bounded treewidth and bounded chordality, The monadic second-order logic of graphs. X: Linear orderings, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Recognizability equals definability for partial k-paths, The complexity of two graph orientation problems, A monadic second-order definition of the structure of convex hypergraphs., The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs, Upper bounds to the clique width of graphs, Circle graphs and monadic second-order logic, The definition in monadic second-order logic of modular decompositions of ordered graphs, Unnamed Item, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Nondeterministic operations on finite relational structures, The monadic second-order logic of graphs. XII: Planar graphs and planar maps, A logic-based approach to incremental reasoning on multi-agent systems, Canonisation and Definability for Graphs of Bounded Rank Width

Cites Work

• Hyperedge replacement: grammars and languages
• Monadic second-order evaluations on tree-decomposable graphs
• On rigid circuit graphs
• The structure of the models of decidable monadic theories of graphs
• Graph minors. V. Excluding a planar graph
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Handle-rewriting hypergraph grammars
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Undecidable theories
• Weak Second‐Order Arithmetic and Finite Automata
• Easy problems for tree-decomposable graphs
• Reachability is harder for directed than for undirected finite graphs
• Graph expressions and graph rewritings
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item