Tractability of quantified temporal constraints to the max
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
A temporal constraint language is a set of relations that are first-order definable over (ℚ; <). We show that several temporal constraint languages whose constraint satisfaction problem is maximally tractable are also maximally tractable for the more expressive quantified constraint satisfaction problem. These constraint languages are defined in terms of preservation under certain binary polymorphisms. We also present syntactic characterizations of the relations in these languages.
Details
Original language | English |
---|---|
Pages (from-to) | 1141-1156 |
Number of pages | 16 |
Journal | International journal of algebra and computation |
Volume | 24 |
Issue number | 8 |
Publication status | Published - 16 Dec 2014 |
Peer-reviewed | Yes |
External IDs
ORCID | /0000-0001-8228-3611/work/142241113 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- constraint satisfaction problems, Highly set-transitive structures, max-closed constraints, quantified constraint satisfaction, temporal constraint languages