Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1204410,
author = {Gajarský, Jakub and Hliněný, Petr and Obdržálek, Jan and Ordyniak, Sebastian},
address = {Berlin},
booktitle = {ISAAC 2014, LNCS 8889},
doi = {http://dx.doi.org/10.1007/978-3-319-13075-0_35},
editor = {Hee-Kap Ahn, Chan-Su Shin},
keywords = {existential first-order logic; parameterized complexity; kernelization; poset embedding},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-319-13074-3},
pages = {441-451},
publisher = {Springer International Publishing},
title = {Faster Existential FO Model Checking on Posets},
year = {2014}
}
TY - JOUR
ID - 1204410
AU - Gajarský, Jakub - Hliněný, Petr - Obdržálek, Jan - Ordyniak, Sebastian
PY - 2014
TI - Faster Existential FO Model Checking on Posets
PB - Springer International Publishing
CY - Berlin
SN - 9783319130743
KW - existential first-order logic
KW - parameterized complexity
KW - kernelization
KW - poset embedding
N2 - We prove that the model checking problem for the existen- tial 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 (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) · n 2 ) 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 comple- ment 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. In Hee-Kap Ahn, Chan-Su Shin. \textit{ISAAC 2014, LNCS 8889}. Berlin: Springer International Publishing, 2014, p.~441-451. ISBN~978-3-319-13074-3. Available from: https://dx.doi.org/10.1007/978-3-319-13075-0\_{}35.
|
