Tractability of quantified temporal constraints to the max

Research output: Contribution to journalResearch articleContributedpeer-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 languageEnglish
Pages (from-to)1141-1156
Number of pages16
JournalInternational journal of algebra and computation
Volume24
Issue number8
Publication statusPublished - 16 Dec 2014
Peer-reviewedYes

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