id: 06101149
dt: a
an: 06101149
au: Gavenčiak, Tomáš; Král, Daniel; Oum, Sang-il
ti: Deciding first order properties of matroids.
so: Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th
    international colloquium, ICALP 2012, Warwick, UK, July 9‒13, 2012.
    Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-31584-8/pbk).
    Lecture Notes in Computer Science 7392, 239-250 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-31585-5_24
ab: Summary: Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion
    of graph classes with locally bounded tree-width and established that
    every first order property can be decided in almost linear time in such
    a graph class. Here, we introduce an analogous notion for matroids
    (locally bounded branch-width) and show the existence of a fixed
    parameter algorithm for first order properties in classes of regular
    matroids with locally bounded branch-width. To obtain this result, we
    show that the problem of deciding the existence of a circuit of length
    at most $k$ containing two given elements is fixed parameter tractable
    for regular matroids.
rv: