Tractability of quantified temporal constraints to the max
2014 (English)In: International journal of algebra and computation, ISSN 0218-1967, Vol. 24, no 8, 1141-1156 p.Article in journal (Refereed) Published
A temporal constraint language is a set of relations that are first-order definable over (Q; less than). 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.
Place, publisher, year, edition, pages
World Scientific Publishing , 2014. Vol. 24, no 8, 1141-1156 p.
Highly set-transitive structures; constraint satisfaction problems; temporal constraint languages; max-closed constraints; quantified constraint satisfaction
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-114258DOI: 10.1142/S0218196714500507ISI: 000348199500004OAI: oai:DiVA.org:liu-114258DiVA: diva2:788596
Funding Agencies|European Research Council Under the European Community ; Swedish Research Council (VR) [621-2012-3239]; Spanish project [TIN2013-46181-C2-2-R]; Basque project [GIU12/26]; Basque grant [UFI11/45]2015-02-162015-02-162015-02-16