Monadic second-order model-checking on decomposable matroids
From MaRDI portal
Publication:548278
DOI10.1016/j.dam.2011.02.005zbMath1225.05073OpenAlexW2963193004MaRDI QIDQ548278
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
monadic second-order logicenumerationfixed-parameter complexitymatroid representationbranch-widthseries-parallel operation
Related Items
Tree automata and pigeonhole classes of matroids. I ⋮ The rank-width of edge-coloured graphs ⋮ Decomposition width of matroids ⋮ Tree automata and pigeonhole classes of matroids. II
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear delay enumeration and monadic second-order logic
- Circumscription - a form of non-monotonic reasoning
- Matroid representation over GF(3)
- A partial k-arboretum of graphs with bounded treewidth
- The excluded minors for GF(4)-representable matroids
- Graph minors. XIII: The disjoint paths problem
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Approximating clique-width and branch-width
- The branchwidth of graphs and their cycle matroids
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Easy problems for tree-decomposable graphs
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- Decomposition Width of 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
- On the inherent intractability of certain coding problems (Corresp.)
- Mathematical Foundations of Computer Science 2003
- On the Complexity of Some Enumeration Problems for Matroids
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Finding Branch-Decompositions and Rank-Decompositions
