ON POINT-BASED TEMPORAL DISJOINTNESS

We address the problems of determining consistency and of finding a so lution for sets of three-point relations expressing exclusion of a poi nt from an interval, and for sets of four-point relations expressing i nterval disjointness. Availability of these relations is an important requirement for dealing with the sorts of temporal constraints encount ered in many AI applications such as plan reasoning. We prove that con sistency testing is NP-complete and finding a solution is NP-hard.