| Identifikační kód | RIV/00216224:14330/15:00081186 |
|---|
| Název v anglickém jazyce | Faster Existential FO Model Checking on Posets |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 4 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Jakub Gajarský (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9663207)
Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099)
Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) |
|---|
| Popis výsledku v anglickém jazyce | 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. Wecomplement this result by showing that, under a certain complexity-theoretical assumption, the existential FO model checking problem does not have a polynomial kernel. |
|---|
| Klíčová slova oddělená středníkem | rst-order logic; partially ordered sets; model checking; parameterized complexity |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.2168/LMCS-11(4:8)2015 |
|---|