The monadic second-order logic of graphs. XV: On a conjecture by D. Seese

DOI10.1016/J.JAL.2005.08.004zbMath1099.03007OpenAlexW2038062006WikidataQ123188693 ScholiaQ123188693MaRDI QIDQ2494727

No author found.

Publication date: 30 June 2006

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

Full work available at URL: https://doi.org/10.1016/j.jal.2005.08.004

zbMATH Keywords

monadic second-order logiccomparability graphline graphdecidable theoryinterval graphclique-widthmonadic second-order transductiontree definability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Graph theory (05C99)

Related Items (10)

Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The rank-width of edge-coloured graphs ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Constrained-path labellings on graphs of bounded clique-width ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Circle graphs and monadic second-order logic ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Betweenness of partial orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Graph minors. V. Excluding a planar graph
• N-free posets as generalizations of series-parallel posets
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• A partial k-arboretum of graphs with bounded treewidth
• Highly connected sets and the excluded grid theorem
• Monadic second-order definable graph transductions: a survey
• The monadic second-order logic of graphs. X: Linear orderings
• Logical description of context-free graph languages
• Efficient graph representations
• A monadic second-order definition of the structure of convex hypergraphs.
• Clique-width of countable graphs: A compactness property.
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Erratum to ``The monadic second-order logic of graphs. VI: On several representations of graphs by relational structures
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Fusion in relational structures and the verification of monadic second-order properties
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Graph Classes: A Survey
• Handbook of Graph Grammars and Computing by Graph Transformation
• Decidability of Second-Order Theories and Automata on Infinite Trees
• LATIN 2004: Theoretical Informatics

This page was built for publication: The monadic second-order logic of graphs. XV: On a conjecture by D. Seese