A New Proof of Tractability for ORD-Horn Relations

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Temporal Resoning

This paper gives an elementary proof of the tractability of a sub-class of temporal relations in Allen’s algebra and related temporal calculi, the class of preconvex relations. In Allen’s case, this subclass coincides with the class of ORD-Horn relations. Nebel and Biirckert defined ORD-Horn relations and proved that path-consistency is a sufficient condition for consistency of a network for this sub-class. We prove a stronger result: for each path-consistent network in the sub-class, we give an effective method for constructing a feasible scenario without backtrack.