Monadic second-order model-checking on decomposable matroids

DOI10.1016/J.DAM.2011.02.005MaRDI QIDQ548278zbMATHOpenAlexFDO

Authors Yann Strozecki

Publication date 28 June 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.02.005

zbMATH Keywords

enumerationmonadic second-order logicfixed-parameter complexitymatroid representationbranch-widthseries-parallel operation

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Decomposition width of matroids
• Decomposition width of matroids
• Branch-width, parse trees, and monadic second-order logic for matroids.
• scientific article; zbMATH DE number 1962824
• Trees, grids, and MSO decidability: from graphs to matroids

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1962835 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Approximating clique-width and branch-width
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Branchwidth of graphic matroids
• Circumscription - a form of non-monotonic reasoning
• Decomposition width of matroids
• Easy problems for tree-decomposable graphs
• Enumeration of the monomials of a polynomial and related complexity classes
• Finding Branch-Decompositions and Rank-Decompositions
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph minors. XIII: The disjoint paths problem
• Linear delay enumeration and monadic second-order logic
• Logic, graphs, and algorithms
• Mathematical Foundations of Computer Science 2003
• Matroid representation over GF(3)
• On the Complexity of Some Enumeration Problems for Matroids
• On the inherent intractability of certain coding problems (Corresp.)
• The branchwidth of graphs and their cycle matroids
• The excluded minors for GF(4)-representable matroids
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

Cited in

(7)

• Decomposition width of matroids
• Trees, grids, and MSO decidability: from graphs to matroids
• Decomposition width of matroids
• The rank-width of edge-coloured graphs
• scientific article; zbMATH DE number 1962824 (Why is no real title available?)
• Tree automata and pigeonhole classes of matroids. II
• Tree automata and pigeonhole classes of matroids. I

This page was built for publication: Monadic second-order model-checking on decomposable matroids

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