Manuel Bodirsky
Discrete Temporal Constraint Satisfaction Problems
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
Abstract
A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.
Citation
Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM, 65(2), Article 9. https://doi.org/10.1145/3154832
Journal Article Type | Article |
---|---|
Acceptance Date | Nov 7, 2017 |
Online Publication Date | Feb 6, 2018 |
Publication Date | Mar 1, 2018 |
Deposit Date | Nov 12, 2017 |
Publicly Available Date | Mar 29, 2024 |
Journal | Journal of the Association for Computing Machinery. |
Print ISSN | 0004-5411 |
Electronic ISSN | 1557-735X |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Peer Reviewed |
Volume | 65 |
Issue | 2 |
Article Number | 9 |
DOI | https://doi.org/10.1145/3154832 |
Files
Accepted Journal Article
(534 Kb)
PDF
Copyright Statement
© 2018 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Journal of the ACM, https://doi.org/10.1145/10.1145/3154832.
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search