scientific article; zbMATH DE number 1059243
Monadic second-order logic is powerful enough for expressing many nonelementary properties of graphs, such as connectivity or planarity, for example, but still it is algorithmically tractable. In this paper, the author surveys the descriptional complexity of some graph properties in terms of various fragments of monadic second-order logic. Special attention is paid to the question whether a property and its negation are expressible in the same fragments. It is also shown that in some cases quantifications over sets of edges increase the expressive power while in others they can be eliminated. Furthermore, it is shown that some properties have negative definitions in terms of forbidden configurations which are simpler than any positive definitions. Finally, some related topics are dicussed and several conjectures are presented. For the entire collection see [Zbl 0865.00055].
- 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
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- Logical description of context-free graph languages
- The monadic second-order logic of graphs. XII: Planar graphs and planar maps
- Map genus, forbidden maps, and monadic second-order logic
- Automatic graphs and D0L-sequences of finite graphs
- Evaluation diversity for graph conditions
- Approximating max-cut under graph-MSO constraints
- Theorem proving graph grammars with attributes and negative application conditions
- The expressibility of fragments of hybrid graph logic on finite digraphs
- On orthogonally guarding orthogonal polygons with bounded treewidth
- Hitting forbidden minors: approximation and kernelization
- Expressive power of monadic logics on words, trees, pictures, and graphs
- Relative expressiveness of the edge/adjacency language for graph theory
- Unfolding Graph Transformation Systems: Theory and Applications to Verification
- Emptiness of ordered multi-pushdown automata is 2ETIME-complete
- GETGRATS: a summary of scientific results (with annotated bibliography)
- Parameterized leaf power recognition via embedding into graph products
- Origin-equivalence of two-way word transducers is in PSPACE
- scientific article; zbMATH DE number 7104937 (Why is no real title available?)
- Evaluation diversity for graph conditions
- Invariant Analysis for Multi-agent Graph Transformation Systems Using k-Induction
- Affine optimal k-proper connected edge colorings
- Parameterized leaf power recognition via embedding into graph products
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)
