Abstract
Different approaches to time granularity have been proposed in the database literature to formalize the notion of calendar, based on algebraic, logical, and string-based formalisms. In this paper, we further develop an alternative approach based on automata, originally proposed in [4], which makes it possible to deal with infinite time granularities in an effective (and efficient) way. In particular, such an approach provides an effective solution to fundamental problems such as equivalence and conversion of time granularities. We focus our attention on two kinds of optimization problems for automaton-based representations, namely, computing the smallest representation and computing the most tractable representation, that is, the one on which crucial algorithms (e.g., granule conversion algorithms) run fastest. We first introduce and compare these two minimization problems; then, we give a polynomial time algorithm that solves the latter.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bettini, C., Jajodia, S., Wang, X.S.: Time Granularities in Databases, Data Mining, and Temporal Reasoning. Springer, Heidelberg (2000)
Calbrix, H., Nivat, M., Podelski, A.: Ultimately periodic words of rational ω-languages. In: Main, M.G., Melton, A.C., Mislove, M.W., Schmidt, D., Brookes, S.D. (eds.) MFPS 1993. LNCS, vol. 802, pp. 554–566. Springer, Heidelberg (1994)
Combi, C., Franceschet, M., Peron, A.: A logical approach to represent and reason about calendars. In: Proceedings of the 9th International Symposium on Temporal Representation and Reasoning, pp. 134–140. IEEE Computer Society Press, Los Alamitos (2002)
Dal Lago, U., Montanari, A.: Calendars, time granularities, and automata. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol. 2121, pp. 279–298. Springer, Heidelberg (2001)
Dal Lago, U., Montanari, A., Puppis, G.: Time granularities, calendar algebra, and automata. Technical Report 4, Dipartimento di Matematica e Informatica, Università degli Studi di Udine, Italy (February 2003)
Dal Lago, U., Montanari, A., Puppis, G.: Towards compact and tractable automaton-based representations of time granularities. Technical Report 17, Dipartimento di Matematica e Informatica, Università degli Studi di Udine, Italy (July 2003)
Dyreson, C.E., Evans, W.S., Lin, H., Snodgrass, R.T.: Efficiently supporting temporal granularities. IEEE Transactions on Knowledge and Data Engineering 12(4), 568–587 (2000)
Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing 6, 323–350 (1977)
Ning, P., Jajodia, S., Wang, X.S.: An algebraic representation of calendars. Annals of Mathematics and Artificial Intelligence 36, 5–38 (2002)
Thomas, W.: Languages, automata, and logic. In: Rozemberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 389–455. Springer, Heidelberg (1997)
Wijsen, J.: A string-based model for infinite granularities. In: Bettini, C., Montanari, A. (eds.) Proceedings of the AAAI Workshop on Spatial and Temporal Granularities, pp. 9–16. AAAI Press, Menlo Park (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dal Lago, U., Montanari, A., Puppis, G. (2003). Towards Compact and Tractable Automaton-Based Representations of Time Granularities. In: Blundo, C., Laneve, C. (eds) Theoretical Computer Science. ICTCS 2003. Lecture Notes in Computer Science, vol 2841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45208-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-45208-9_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20216-5
Online ISBN: 978-3-540-45208-9
eBook Packages: Springer Book Archive