LATTICE STRUCTURE OF TEMPORAL INTERVAL RELATIONS

Due to increasing interest in representation of temporal knowledge, au tomation of temporal reasoning, and analysis of distributed systems, l iterally dozens of temporal models have been proposed and explored dur ing the last decade. Interval-based temporal models are especially app ealing when reasoning about events with temporal extent but pose speci al problems when deducing possible relationships among events. The pap er delves deeply into the structure of the set of atomic relations in a class of temporal interval models assumed to satisfy density and hom ogeneity properties. An order structure is imposed on the atomic relat ions of a given model allowing the characterization of the composition s of atomic relations (or even lattice intervals) as lattice intervals . By allowing the utilization of lattice intervals rather than individ ual relations, this apparently abstract result explicitly leads to a c oncrete approach which speeds up constraint propagation algorithms.