FO Model Checking on Posets of Bounded Width

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00081183" target="_blank" >RIV/00216224:14330/15:00081183 - isvavai.cz</a>

Výsledek na webu

<a href="http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7352273" target="_blank" >http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7352273</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS.2015.63" target="_blank" >10.1109/FOCS.2015.63</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FO Model Checking on Posets of Bounded Width

Popis výsledku v původní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.

Název v anglickém jazyce

FO Model Checking on Posets of Bounded Width

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-03501S" target="_blank" >GA14-03501S: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

56th Annual Symposium on Foundations of Computer Science, FOCS 2015

ISBN

9781467381918

ISSN

0272-5428

e-ISSN

—

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

1. 1. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—