scientific article; zbMATH DE number 1059243

zbMATH Open0883.03004MaRDI QIDQ4353558FDOQ4353558

Bruno Courcelle

Publication date: 23 March 1998

Title of this publication is not available (Why is that?)

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

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)

Cited In (24)

• Map genus, forbidden maps, and monadic second-order logic
• Automatic graphs and D0L-sequences of finite graphs
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Evaluation diversity for graph conditions
• Invariant Analysis for Multi-agent Graph Transformation Systems Using k-Induction
• Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete
• Theorem proving graph grammars with attributes and negative application conditions
• The expressibility of fragments of hybrid graph logic on finite digraphs
• Title not available (Why is that?)
• Parameterized Leaf Power Recognition via Embedding into Graph Products
• Regular transducer expressions for regular transformations
• Relative expressiveness of the edge/adjacency language for graph theory
• On orthogonally guarding orthogonal polygons with bounded treewidth
• Unfolding Graph Transformation Systems: Theory and Applications to Verification
• Logical description of context-free graph languages
• Parameterized shifted combinatorial optimization
• Evaluation diversity for graph conditions
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Parameterized leaf power recognition via embedding into graph products
• Origin-equivalence of two-way word transducers is in PSPACE
• On the planar split thickness of graphs
• Approximating max-cut under graph-MSO constraints
• GETGRATS
• Hitting forbidden minors: approximation and kernelization

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)