scientific article; zbMATH DE number 1059243

MaRDI QIDQ4353558zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 23 March 1998

zbMATH Keywords

descriptional complexityexpressive powerforbidden configurationsgraph propertiesfragments of monadic second-order logic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order model theory (03C85)

Recommendations

• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• On the Expressive Power of Graph Logic
• Graph equivalences and decompositions definable in monadic second-order logic. The case of circle graphs
• Expressive power of monadic logics on words, trees, pictures, and graphs

Cited in

(22)

• Hitting forbidden minors: approximation and kernelization
• Emptiness of ordered multi-pushdown automata is 2ETIME-complete
• Evaluation diversity for graph conditions
• Relative expressiveness of the edge/adjacency language for graph theory
• Evaluation diversity for graph conditions
• On orthogonally guarding orthogonal polygons with bounded treewidth
• Parameterized leaf power recognition via embedding into graph products
• Unfolding Graph Transformation Systems: Theory and Applications to Verification
• Parameterized leaf power recognition via embedding into graph products
• Origin-equivalence of two-way word transducers is in PSPACE
• Map genus, forbidden maps, and monadic second-order logic
• The expressibility of fragments of hybrid graph logic on finite digraphs
• Invariant Analysis for Multi-agent Graph Transformation Systems Using k-Induction
• GETGRATS: a summary of scientific results (with annotated bibliography)
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Theorem proving graph grammars with attributes and negative application conditions
• Expressive power of monadic logics on words, trees, pictures, and graphs
• scientific article; zbMATH DE number 7104937 (Why is no real title available?)
• Automatic graphs and D0L-sequences of finite graphs
• Logical description of context-free graph languages
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Approximating max-cut under graph-MSO constraints

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4353558)