With Jan Kára. Preprint, 2006.
We introduce two new tractable temporal constraint languages, which both strictly contain the Ord-Horn language of Buerkert and Nebel. Our algorithm decides whether a given set of constraints from these languages is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) the two languages cannot be solved by Datalog or by establishing local consistency.
Postscript and Pdf
A related talk at the satellite workshop of CSL'06 on Logic and Combinatorics in Szeged, and at the workshop Complexity of Constraints in Dagstuhl. In Postscript and in Pdf.