Compact and Tractable Automaton-based Representations of Time Granularities

Most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms [11]. Here we follow an alternative automaton-based approach, originally outlined in [7], 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.