Tractability of quantified temporal constraints to the max

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
Seiten (von - bis)1141-1156
Seitenumfang16
FachzeitschriftInternational journal of algebra and computation
Jahrgang24
Ausgabenummer8
PublikationsstatusVeröffentlicht - 16 Dez. 2014
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0001-8228-3611/work/142241113

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • constraint satisfaction problems, Highly set-transitive structures, max-closed constraints, quantified constraint satisfaction, temporal constraint languages