Monadic second-order model-checking on decomposable matroids

DOI10.1016/J.DAM.2011.02.005zbMATH Open1225.05073OpenAlexW2963193004MaRDI QIDQ548278FDOQ548278

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

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

Cited In (7)

• Trees, grids, and MSO decidability: from graphs to matroids
• Decomposition width of matroids
• Title not available (Why is that?)
• Decomposition width of matroids
• Tree automata and pigeonhole classes of matroids. II
• Tree automata and pigeonhole classes of matroids. I
• The rank-width of edge-coloured graphs

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)