Computational complexity of relating time points with intervals

✍ Scribed by Peter Jonsson; Thomas Drakengren; Christer Bäckström

• Book ID: 104105517
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 190 KB
• Volume: 109
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(99)00007-7

✦ Synopsis

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 4 294 967 296 subclasses. This article completely determines the computational complexity of these subclasses and it identifies all of the maximal tractable subalgebras-five in total.