Yann Strozecki

  1. A Logical Approach to Decomposable Matroids.

    Authors: Yann Strozecki
    Subjects: Computational Complexity
    Abstract

    A notion of branch-width may be defined for matroids, which generalizes the
    one known for graphs. We first give a proof of the polynomial time model
    checking of MSOM on representable matroids of bounded branch-width, by
    reduction to MSO on trees, much simpler than the one previously known. We
    deduce results about spectrum of MSOM formulas and enumeration on matroids of
    bounded branch-width. We also provide a link between our logical approach and a
    grammar that allows to build matroids of bounded branch-width.

Syndicate content