Computational complexity of relating time points with intervals

Several algebras have been proposed for reasoning about qualitative constraints over the time line. One of these algebras is Vilain's point–interval algebra, which can relate time points with time intervals. Apart from being a stand-alone qualitative algebra, it is also used as a subalgebra in Meiri's approach to temporal reasoning, which combines reasoning about metric and qualitative temporal constraints over both time points and time intervals. While the satisfiability problem for the full point–interval algebra is known to be NP-complete, not much is known about its 4294967296 subclasses. This article completely determines the computational complexity of these subclasses and it identifies all of the maximal tractable subalgebras—five in total.

Authors

• Peter Jonsson Linköping University
• Thomas Drakengren Peter Jonsson
• Christer Bäckström

Keywords

• Temporal reasoning
• Constraint satisfaction
• Point–interval algebra
• Algorithms
• Complexity