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

DOI10.1016/J.TCS.2005.10.006zbMATH Open1093.03006OpenAlexW1999958048MaRDI QIDQ820150FDOQ820150

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• Rabin's theorem in the concurrency setting: a conjecture
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Title not available (Why is that?)
• 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)