FO Model Checking on Posets of Bounded Width (2015)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/15:00081183 |
|---|---|
| Název v anglickém jazyce | FO Model Checking on Posets of Bounded Width |
| Druh | D - Článek ve sborníku |
| 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 | 7 |
| 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) M. S. Ramanujan (státní příslušnost: IN - Indická republika) Daniel Lokshtanov (státní příslušnost: NO - Norské království) Saket Saurabh (státní příslušnost: IN - Indická republika) |
| Popis výsledku v anglickém jazyce | Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes ofgraphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. |
| Klíčová slova oddělená středníkem | model checking; first-order logic; posets; width; metatheorem |
| Stránka www, na které se nachází výsledek | http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7352273 |
| DOI výsledku | 10.1109/FOCS.2015.63 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 |
|---|---|
| ISBN | 9781467381918 |
| ISSN | 0272-5428 |
| Počet stran výsledku | 12 |
| Strana od-do | 963-974 |
| Název nakladatele | IEEE Computer Society |
| Místo vydání | Berkeley, CA, USA |
| Místo konání akce | Berkeley, CA, USA |
| Datum konání akce | 2015 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2016 |
| Specifikace | RIV/00216224:14330/15:00081183!RIV16-MSM-14330___ |
| Datum poslední aktualizace výsledku | 24.05.2016 |
| Kontrolní číslo | 191636309 |
Informace o dalších výskytech výsledku dodaného stejným předkladatelem
| Dodáno GA ČR v roce 2016 | RIV/00216224:14330/15:00081183 v dodávce dat RIV16-GA0-14330___/01:1 |
|---|
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GA | GA14-03501S - Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky (2014 - 2016) |
|---|---|
| Podpora / návaznosti | Specifický výzkum na vysokých školách, poskytovatel MŠMT |