Most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms. 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 previous termtractablenext term representation of it, that is, the one on which crucial algorithms, such as granule conversion algorithms, run fastest.
Compact and Tractable Automaton-based Representations for Time Granularities
DAL LAGO, UGO;
2007
Abstract
Most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms. 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 previous termtractablenext term representation of it, that is, the one on which crucial algorithms, such as granule conversion algorithms, run fastest.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
