| BOVA, Simone, Robert GANIAN and Stefan SZEIDER. Quantified conjunctive queries on partially ordered sets. Theoretical Computer Science. Amsterdam: Elsevier, 2016, vol. 618, No 1, p. 72-84. ISSN 0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2016.01.010. |
Other formats:
BibTeX
LaTeX
RIS
@article{1376001,
author = {Bova, Simone and Ganian, Robert and Szeider, Stefan},
article_location = {Amsterdam},
article_number = {1},
doi = {http://dx.doi.org/10.1016/j.tcs.2016.01.010},
keywords = {Quantified conjunctive queries; Posets; Parameterized complexity; Model checking},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Quantified conjunctive queries on partially ordered sets},
volume = {618},
year = {2016}
}
TY - JOUR
ID - 1376001
AU - Bova, Simone - Ganian, Robert - Szeider, Stefan
PY - 2016
TI - Quantified conjunctive queries on partially ordered sets
JF - Theoretical Computer Science
VL - 618
IS - 1
SP - 72-84
EP - 72-84
PB - Elsevier
SN - 03043975
KW - Quantified conjunctive queries
KW - Posets
KW - Parameterized complexity
KW - Model checking
N2 - We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finite poset (a reflexive, antisymmetric, and transitive directed graph). We prove that the problem is already NP-hard on a certain fixed poset, and investigate structural properties of posets yielding fixed-parameter tractability when the problem is parameterized by the query. Our main algorithmic result is that model checking quantified conjunctive queries on posets is fixed-parameter tractable when parameterized by the sentence and the width of the poset (the maximum size of a subset of pairwise incomparable elements). We complement our algorithmic result by complexity results with respect to classes of finite posets in a hierarchy of natural poset invariants, establishing its tightness in this sense. (C) 2016 Elsevier B.V. All rights reserved.
ER -
BOVA, Simone, Robert GANIAN and Stefan SZEIDER. Quantified conjunctive queries on partially ordered sets. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2016, vol.~618, No~1, p.~72-84. ISSN~0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2016.01.010.
|
