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.
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 | Nov 13, 2017 |
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 |
Public URL | https://durham-repository.worktribe.com/output/1344238 |
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
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Partitioning H-free graphs of bounded diameter
(2021)
Presentation / Conference Contribution
QCSP on reflexive tournaments
(2021)
Presentation / Conference Contribution
Injective colouring for H-free graphs
(2021)
Presentation / Conference Contribution
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