Trees, grids, and MSO decidability: from graphs to matroids

DOI10.1016/j.tcs.2005.10.006zbMath1093.03006OpenAlexW1999958048MaRDI QIDQ820150

Petr Hliněný, Detlef Seese

Publication date: 6 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.006

zbMATH Keywords

spikesgraphmonadic second-order logicgridsdecidabilitymatroidinterpretabilityclique-widthtree-widthbranch-width

Mathematics Subject Classification ID

Related Items (5)

Tree automata and pigeonhole classes of matroids. I ⋮ Matroid tree-width ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ On the width of regular classes of finite structures

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Notes on monadic logic. Part B: Complexity of linear orders in ZFC
• The monadic theory and the next world
• Monadic theory of order and topology. II
• Recognizing graphic matroids
• Graph minors. X: Obstructions to tree-decomposition
• Set theory. An introduction to large cardinals
• The monadic theory of order
• Monadic theory of order and topology, I
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. X: Linear orderings
• On the excluded minors for the matroids of branch-width \(k\)
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Branch-width and well-quasi-ordering in matroids and graphs.
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Structural properties of context-free sets of graphs generated by vertex replacement
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• Interpretierbarkeit in der Gruppentheorie
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The first order properties of products of algebraic systems
• Weak Second‐Order Arithmetic and Finite Automata
• The monadic theory of ω₂
• Easy problems for tree-decomposable graphs
• On the strength of the interpretation method
• Monadic theory of order and topology in ZFC
• Complexity of Finding Embeddings in a k-Tree
• Handbook of Graph Grammars and Computing by Graph Transformation
• The Undecidability of Theories of Groupoids with an Extra Predicate
• Parameterized and Exact Computation
• Mathematical Foundations of Computer Science 2003
• A Parametrized Algorithm for Matroid Branch-Width
• Decidability of Second-Order Theories and Automata on Infinite Trees
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Trees, grids, and MSO decidability: from graphs to matroids