Other formats:
BibTeX
LaTeX
RIS
@article{1316744,
author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian},
article_location = {Německo},
article_number = {4},
doi = {http://dx.doi.org/10.2168/LMCS-11(4:8)2015},
keywords = {rst-order logic; partially ordered sets; model checking; parameterized complexity},
language = {eng},
issn = {1860-5974},
journal = {Logical Methods in Computer Science},
title = {Faster Existential FO Model Checking on Posets},
url = {http://arxiv.org/pdf/1409.4433.pdf},
volume = {11},
year = {2015}
}
TY - JOUR
ID - 1316744
AU - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian
PY - 2015
TI - Faster Existential FO Model Checking on Posets
JF - Logical Methods in Computer Science
VL - 11
IS - 4
SP - 1-13
EP - 1-13
PB - Logical Methods in Computer Science e.V.
SN - 18605974
KW - rst-order logic
KW - partially ordered sets
KW - model checking
KW - parameterized complexity
UR - http://arxiv.org/pdf/1409.4433.pdf
N2 - We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the formula and the width of a poset (the maximum size of an antichain). While there is a long line of research into FO model checking on graphs, the study of this problem on posets has been initiated just recently by Bova, Ganian and Szeider (CSL-LICS 2014), who proved that the existential fragment of FO has an FPT algorithm for a poset of fixed width. We improve upon their result in two ways: (1) the runtime of our algorithm is O(f(|\phi|,w)*n2) on n-element posets of width w, compared to O(g(|\phi|)*n^{h(w)}) of Bova et al., and (2) our proofs are simpler and easier to follow. We complement this result by showing that, under a certain complexity-theoretical assumption, the existential FO model checking problem does not have a polynomial kernel.
ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ, Jan OBDRŽÁLEK and Sebastian ORDYNIAK. Faster Existential FO Model Checking on Posets. \textit{Logical Methods in Computer Science}. Německo: Logical Methods in Computer Science e.V., 2015, vol.~11, No~4, p.~1-13. ISSN~1860-5974. Available from: https://dx.doi.org/10.2168/LMCS-11(4:8)2015.
|
