2009/08/31 by Yann Strozecki, Strozecki, Yann · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.DM #cs.DS #cs.LO
paper · pdf · doi:10.48550/arxiv.0908.4499
32 pages, journal paper. Revision: the last part has been removed and the writing improved
arxiv created 2011/01/29 · arxiv updated 2015/03/13
A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.