View Related Documents

Abstract

A positive temporal template (or a positive temporal constraint language) is a relational structure whose relations can be defined over countable dense linear order without endpoints using a relational symbol ≤, logical conjunction and disjunction. This paper gives a complete complexity characterization for quantified constraint satisfaction problems (QCSP) over positive temporal languages. Although the constraint satisfaction problem (CSP) for an arbitrary positive temporal language is trivial (all these templates are closed under constant functions), the corresponding QCSP problems are decidable in LOGSPACE or complete for one of the following classes: NLOGSPACE, P, NP or PSPACE.
Work partially supported by Polish Ministry of Science and Education grant 3 T11C 042 30.

Fulltext Preview

Image of the first page of the fulltext document