FO Model Checking on Posets of Bounded Width
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
FO Model Checking on Posets of Bounded Width
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-03501S" target="_blank" >GA14-03501S: Parameterized algorithms and kernelization in the context of discrete mathematics and logic</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
56th Annual Symposium on Foundations of Computer Science, FOCS 2015
ISBN
9781467381918
ISSN
0272-5428
e-ISSN
—
Number of pages
12
Pages from-to
963-974
Publisher name
IEEE Computer Society
Place of publication
Berkeley, CA, USA
Event location
Berkeley, CA, USA
Event date
Jan 1, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—