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

DOI10.1016/J.TCS.2005.10.006MaRDI QIDQ820150zbMATH OpenOpenAlexFDO

Authors 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

graphinterpretabilityspikesclique-widthdecidabilitygridsmatroidmonadic second-order logictree-widthbranch-width

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Decidability of theories and sets of sentences (03B25)

Recommendations

• Parameterized and Exact Computation
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 1962824
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Monadic second-order model-checking on decomposable matroids

Cites work

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

Cited in

(12)

• On axiomatizability of the class of finitary matroids and decidability of their universal theory
• scientific article; zbMATH DE number 1962824 (Why is no real title available?)
• Monadic second-order model-checking on decomposable matroids
• Mathematical Foundations of Computer Science 2003
• Rabin's theorem in the concurrency setting: a conjecture
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• scientific article; zbMATH DE number 6678444 (Why is no real title available?)
• Tree automata and pigeonhole classes of matroids. I
• MSO undecidability for hereditary classes of unbounded clique-width
• Parameterized and Exact Computation
• On the width of regular classes of finite structures
• Matroid tree-width

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

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