Discrete Temporal Constraint Satisfaction Problems.
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 113214
- Type
- D - Journal article
- DOI
-
10.1145/3154832
- Title of journal
- Journal of the ACM
- Article number
- 9
- First page
- -
- Volume
- 65
- Issue
- 2
- ISSN
- 00045411
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2018
- URL
-
https://doi.org/10.1145/3154832
- 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
-
2
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Pioneers the application of Universal Algebra through Model Theory to infinite-domain Constraint Satisfaction Problems (CSPs) as advocated originally in the LICS 2010 paper "On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction" (10.1109/LICS.2010.13). It is the first complete infinite-domain CSP computational complexity classification outside of omega-categorical constraint languages. The first for a class needing model-theoretic methods. It applies in detail newly-developed mathematical methods for the study of infinite-domain CSPs over the integers using quantifier elimination in an enhanced language. This is pursued in subsequent work, e.g. "The Complexity of Disjunctive Linear Diophantine Constraints" (10.4230/LIPIcs.MFCS.2018.33) at MFCS 2018.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -