Compact and tractable automaton-based representations of time granularities

AbstractMost approaches to time granularity proposed in the literature are based on algebraic and logical formalisms [J. Euzenat, A. Montanari, Time granularity, in: M. Fisher, D. Gabbay, L. Vila (Eds.), Handbook of Temporal Reasoning in Artificial Intelligence, Elsevier, 2005, pp. 59–118]. Here we follow an alternative automaton-based approach, originally outlined in [U. Dal Lago, A. Montanari, Calendars, time granularities, and automata, in: Proceedings of the 7th International Symposium on Spatial and Temporal Databases, SSTD, in: LNCS, vol. 2121, Springer, 2001, pp. 279–298], which makes it possible to deal with infinite time granularities in an effective and efficient way. Such an approach provides a neat solution to fundamental algorithmic problems, such as the granularity equivalence and granule conversion problems, which have been often neglected in the literature. In this paper, we focus our attention on two basic optimization problems for the automaton-based representation of time granularities, namely, the problem of computing the smallest representation of a time granularity and that of computing the most tractable representation of it, that is, the one on which crucial algorithms, such as granule conversion algorithms, run fastest