Deciding first order properties of matroids
From MaRDI portal
Publication:3167015
DOI10.1007/978-3-642-31585-5_24zbMATH Open1367.03022arXiv1108.5457OpenAlexW2281935918MaRDI QIDQ3167015FDOQ3167015
Authors: Tomáš Gavenčiak, Sang-Il Oum, Daniel Král' 
Publication date: 1 November 2012
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: 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 logic 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 logic 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.
Full work available at URL: https://arxiv.org/abs/1108.5457
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Decidability of theories and sets of sentences (03B25)
Cited In (7)
- Decomposition width of matroids
- Decomposition width of matroids
- Tree automata and pigeonhole classes of matroids. I
- Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
- First order convergence of matroids
- On the number of circuits in regular matroids (with connections to lattices and codes)
- Covering Vectors by Spaces: Regular Matroids
This page was built for publication: Deciding first order properties of matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167015)
