A general framework for time granularity and its application to temporal reasoning

This paper presents a general framework to define time granularity systems. We identify the main dimensions along which different systems can be characterized, and investigate the formal relationships among granularities in these systems. The paper also introduces the notion of a network of temporal constraints with (multiple) granularities emphasizing the semantic and computational differences from constraint networks with a single granularity. Consistency of networks with multiple granularities is shown to beNP‐hard in general and approximate solutions for this problem and for the minimal network problem are proposed. This revised version was published online in June 2006 with corrections to the Cover Date.