The Library
FO model checking on posets of bounded width
Tools
Gajarsky, Jakub, Hlineny, Petr , Lokshtanov, Daniel , Obdrálek, Jan, Ordyniak, Sebastian, Ramanujan, Maadapuzhi Sridharan and Saurabh, Saket (2015) FO model checking on posets of bounded width. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, Berkeley, CA, USA, 17-20 Oct 2015. Published in: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) pp. 963-974. ISBN 9781467381918. doi:10.1109/FOCS.2015.63 ISSN 0272-5428.
|
PDF
WRAP-FO-model-checking-Posets-Ramanujan-2015.pdf - Accepted Version - Requires a PDF viewer. Download (566Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS.2015.63
Abstract
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 of graphs [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. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset Ρ of width ω and an FO logic formula φ, and determines whether φ holds on P in time f(φ,ω)∙n².
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | First-order logic, Computer systems -- Verification, Computer software -- Verification, Computational complexity, Partially ordered sets, Computer algorithms | ||||||
Series Name: | Annual IEEE Symposium on Foundations of Computer Science | ||||||
Journal or Publication Title: | 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) | ||||||
Publisher: | IEEE Computer Society | ||||||
ISBN: | 9781467381918 | ||||||
ISSN: | 0272-5428 | ||||||
Official Date: | 17 December 2015 | ||||||
Dates: |
|
||||||
Page Range: | pp. 963-974 | ||||||
DOI: | 10.1109/FOCS.2015.63 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 19 January 2018 | ||||||
Date of first compliant Open Access: | 22 January 2018 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Berkeley, CA, USA | ||||||
Date(s) of Event: | 17-20 Oct 2015 | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year