A New Proof of Tractability for ORD-Horn Relations

Gérard Ligozat

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.