FO model checking on posets of bounded width
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 6112
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2015.63
- Title of conference / published proceedings
- IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
- First page
- 963
- Volume
- -
- Issue
- -
- ISSN
- 0272-5428
- Open access status
- Out of scope for open access requirements
- Month of publication
- December
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
6
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 8
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Appearing at one of the two top conferences in theoretical computer science, this paper resolved the open problem of model checking a fixed FO formula on partially-ordered sets of constant width in uniformly-polynomial time. Although the significance of understanding FO model checking on dense structures had been widely recognized (Grohe, in "Logic and Automata", 2008), this frontier had remained largely uncharted prior to this work. This paper spurred an intensive exploration of FO model checking on dense structures, e.g., by Hliněný et al. (IPEC'17), who apply this result in their work on geometric graphs, and Gajarský et al. (LICS'16, ICALP'18).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -