A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning
- Resource Type
- Working Paper
- Authors
- Bodirsky, Manuel; Kara, Jan
- Source
- Subject
- Computer Science - Artificial Intelligence
Computer Science - Logic in Computer Science
I.2.4
- Language
We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.
Comment: 19 pages, 1 figure