FO Model Checking on Posets of Bounded Width
- Submitting institution
-
The University of Sheffield
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2501
- Type
- E - Conference contribution
- DOI
-
10.1109/focs.2015.63
- Title of conference / published proceedings
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- First page
- 963
- Volume
- -
- Issue
- -
- ISSN
- 0272-5428
- Open access status
- Out of scope for open access requirements
- Month of publication
- October
- 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)
-
A - Algorithms
- Citation count
- 8
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- First-Order Logic Model Checking provides foundations for research areas including databases, semantic web, and verification. We present the first tractability result for dense structures (for partially ordered sets), generalising known results (LMCS: doi.org/10.2168/LMCS-11(4:11)2015) which implies tractability for various graph classes (CGJ: https://tinyurl.com/y5zgxqv8). Apart from developing a dynamic variant of Gaifman's celebrated locality theorem, our work has initiated research into dense structures resulting in follow-up papers (https://tinyurl.com/y5c6bjjx, https://tinyurl.com/yxb4jsjn).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -