| Identifikační kód | RIV/00216224:14330/14:00074016 |
|---|
| Název v anglickém jazyce | Faster Existential FO Model Checking on Posets |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2014 |
|---|
| 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 | 1 |
|---|
| 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 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). Whilethere 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. |
|---|
| Klíčová slova oddělená středníkem | existential first-order logic; parameterized complexity; kernelization; poset embedding |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-319-13075-0_35 |
|---|