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.