{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T04:34:43Z","timestamp":1648614883059},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2009,3,18]],"date-time":"2009-03-18T00:00:00Z","timestamp":1237334400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s00236-009-0094-7","type":"journal-article","created":{"date-parts":[[2009,3,17]],"date-time":"2009-03-17T11:14:35Z","timestamp":1237288475000},"page":"331-360","source":"Crossref","is-referenced-by-count":4,"title":["A theory of ultimately periodic languages and automata with an application to time granularity"],"prefix":"10.1007","volume":"46","author":[{"given":"Davide","family":"Bresolin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,3,18]]},"reference":[{"key":"94_CR1","doi-asserted-by":"crossref","unstructured":"Bresolin, D., Montanari, A., Puppis, G.: Time granularities and ultimately periodic automata. In: Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA). Lecture Notes in Artificial Intelligence, vol. 3229, pp. 513\u2013525. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30227-8_43"},{"key":"94_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04228-1","volume-title":"Time Granularities in Databases, Data Mining, and Temporal Reasoning","author":"C. Bettini","year":"2000","unstructured":"Bettini C., Jajodia S., Wang X.: Time Granularities in Databases, Data Mining, and Temporal Reasoning. Springer, Heidelberg (2000)"},{"issue":"1\u20133","key":"94_CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2006.02.019","volume":"360","author":"S. Demri","year":"2006","unstructured":"Demri S.: LTL over integer periodicity constraints. Theor. Comput. Sci. 360(1\u20133), 96\u2013123 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR4","doi-asserted-by":"crossref","unstructured":"Dal Lago, U., Montanari, A.: Calendars, time granularities, and automata. In: Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD). Lecture Notes in Computer Science, vol. 2121, pp. 279\u2013298. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-47724-1_15"},{"key":"94_CR5","unstructured":"Leban, B., McDonald, D., Foster, D.: A representation for collections of temporal intervals. In: Proceedings of the AAAI National Conference on Artificial Intelligence, vol. 1, pp. 367\u2013371. AAAI Press, New York (1986)"},{"key":"94_CR6","unstructured":"Niezette, M., Stevenne, J.: An efficient symbolic representation of periodic time. In: Proceedings of the International Conference on Information and Knowledge Management (CIKM), pp. 161\u2013168. Association for Computing Machinery, New York (1992)"},{"key":"94_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1015835418881","volume":"36","author":"P. Ning","year":"2002","unstructured":"Ning P., Jajodia S., Wang X.: An algebraic representation of calendars. Ann. Math. Artif. Intell. 36, 5\u201338 (2002)","journal-title":"Ann. Math. Artif. Intell."},{"key":"94_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1093\/logcom\/14.1.51","volume":"14","author":"C. Combi","year":"2004","unstructured":"Combi C., Franceschet M., Peron A.: Representing and reasoning about temporal granularities. J. Logic Comput. 14, 51\u201377 (2004)","journal-title":"J. Logic Comput."},{"key":"94_CR9","doi-asserted-by":"crossref","unstructured":"Emerson, E.: Temporal and modal logic. In: Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, pp. 995\u20131072. Elsevier\/MIT Press, Amsterdam\/Cambridge (1990)","DOI":"10.1016\/B978-0-444-88074-1.50021-4"},{"key":"94_CR10","unstructured":"Wijsen, J.: A string-based model for infinite granularities. In: Proceedings of the AAAI Workshop on Spatial and Temporal Granularities, pp. 9\u201316. AAAI Press, New York (2000)"},{"key":"94_CR11","doi-asserted-by":"crossref","unstructured":"Dal Lago, U., Montanari, A., Puppis, G.: Towards compact and tractable automaton-based representations of time granularity. In: Proceedings of the 8th Italian Conference on Theoretical Computer Science (ICTCS). Lecture Notes in Computer Science, vol. 2841, pp. 72\u201385. Springer, Heidelberg (2003)","DOI":"10.1007\/978-3-540-45208-9_7"},{"issue":"1\u20132","key":"94_CR12","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.014","volume":"373","author":"U. Dal Lago","year":"2007","unstructured":"Dal Lago U., Montanari A., Puppis G.: Compact and tractable automaton-based representations for time granularities.. Theor. Comput. Sci. 373(1\u20132), 115\u2013141 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR13","doi-asserted-by":"crossref","unstructured":"Dal Lago, U., Montanari, A., Puppis, G.: On the equivalence of automaton-based representations of time granularities. In: Proceedings of the 14th International Symposium on Temporal Representation and Reasoning (TIME), pp. 82\u201393. IEEE Computer Society, New York (2007)","DOI":"10.1109\/TIME.2007.56"},{"key":"94_CR14","unstructured":"Puppis, G.: Automata for branching and layered temporal structures. Ph.D. thesis, Department of Mathematics and Computer Science, Udine University, Udine, Italy (CS 2006\/08). Available at: http:\/\/users.dimi.uniud.it\/~gabriele.puppis\/files\/PhDThesis.pdf"},{"key":"94_CR15","unstructured":"B\u00fcchi, J.: On a decision method in restricted second order arithmetic. In: Proceedings of the International Congress for Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford University Press, Stanford (1962)"},{"key":"94_CR16","doi-asserted-by":"crossref","unstructured":"Calbrix, H., Nivat, M., Podelski, A.: Ultimately periodic words of rational \u03c9-languages. In: Proceedings of the 9th International Conference on Mathematical Foundations of Programming Semantics. Lecture Notes in Computer Science, vol. 802, pp. 554\u2013566. Springer, Heidelberg (1994)","DOI":"10.1007\/3-540-58027-1_27"},{"key":"94_CR17","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0304-3975(85)90159-8","volume":"40","author":"R. Paige","year":"1985","unstructured":"Paige R., Tarjan R., Bonic R.: A linear time solution to the single function coarsest partition problem. Theor. Comput. Sci. 40, 67\u201384 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR18","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. Knuth","year":"1977","unstructured":"Knuth D., Morris J., Pratt V.: Fast pattern matching in strings. SIAM J. Comput. 6, 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"4\u20135","key":"94_CR19","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/0020-0190(80)90149-0","volume":"10","author":"K. Booth","year":"1980","unstructured":"Booth K.: Lexicographically least circular substrings.. Inf. Process. Lett. 10(4\u20135), 240\u2013242 (1980)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"94_CR20","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0196-6774(81)90013-4","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Shiloach Y.: Fast canonization of circular strings. J. Algorithm 2(2), 107\u2013121 (1981)","journal-title":"J. Algorithm"},{"key":"94_CR21","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. Hopcroft","year":"2001","unstructured":"Hopcroft J., Motwani R., Ullman J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Longman Publishing Co. Inc., Reading (2001)"},{"key":"94_CR22","doi-asserted-by":"crossref","unstructured":"Campeanu, C., II, K.C., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Proceedings of the 4th International Workshop on Implementing Automata (WIA). Lecture Notes in Computer Science, vol. 2214, pp. 60\u201370. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-45526-4_6"},{"key":"94_CR23","first-page":"529","volume":"12","author":"J. Brzozowski","year":"1962","unstructured":"Brzozowski J.: Canonical regular expressions and minimal state graphs for definite events.. Math. Theory Automata 12, 529\u2013561 (1962)","journal-title":"Math. Theory Automata"},{"key":"94_CR24","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(87)90008-9","volume":"49","author":"A. Sistla","year":"1987","unstructured":"Sistla A., Vardi M., Wolper P.: The complementation problem for B \u00fcchi automata with applications to temporal logic. Theor. Comput. Sci. 49, 217\u2013237 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR25","doi-asserted-by":"crossref","unstructured":"L\u00f6ding, C.: Optimal bounds for the transformation of omega-automata. In: Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science, vol. 1738, pp. 97\u2013109. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-46691-6_8"},{"key":"94_CR26","unstructured":"Michel, M.: Complementation is more difficult with automata on infinite words (1988). CNET, Paris, Manuscript"},{"issue":"1\u20132","key":"94_CR27","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(94)00214-4","volume":"141","author":"D. Muller","year":"1995","unstructured":"Muller D., Schupp P.: Simulating alternating tree automata by non-deterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra.. Theor. Comput. Sci. 141(1\u20132), 69\u2013107 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR28","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of \u03c9-automata. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 319\u2013327. IEEE Computer Society, New York (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"94_CR29","unstructured":"Safra, S.: Complexity of automata on infinite objects. Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel (1989)"},{"key":"94_CR30","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","volume":"32","author":"S. Miyano","year":"1984","unstructured":"Miyano S., Hayashi T.: Alternating finite automata on \u03c9-words. Theor. Comput. Sci. 32, 321\u2013330 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR31","doi-asserted-by":"crossref","unstructured":"L\u00f6ding, C., Thomas, W.: Alternating automata and logics over infinite words. In: Proceedings of the IFIP International Conference on Theoretical Computer Science (IFIP TCS), Exploring new frontiers of theoretical informatics. Lecture Notes in Computer Science, vol. 1872, pp. 521\u2013535. Springer, Heidelberg (2000)","DOI":"10.1007\/3-540-44929-9_36"},{"key":"94_CR32","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou C.: Computational Complexity. Addison-Wesley Longman Publishing Co., Inc, Reading (1994)"},{"issue":"6","key":"94_CR33","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang T., Ravikumar B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"94_CR34","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1109\/T-C.1970.222994","volume":"19","author":"T. Kameda","year":"1970","unstructured":"Kameda T., Weiner P.: On the state minimization of nondeterministic finite automata. IEEE Trans. Comput. 19(7), 617\u2013627 (1970)","journal-title":"IEEE Trans. Comput."},{"key":"94_CR35","unstructured":"Matz, O., Potthoff, A.: Computing small nondeterministic automata. In: Proceedings of the Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), BRICS Notes Series, pp. 74\u201388 (1995)"},{"key":"94_CR36","unstructured":"Loma Linda International Heart Institute: Pediatric heart transplantation protocol. Tech. rep., International Heart Institute, Loma Linda University Medical Center, Loma Linda, CA (2002). Available at: http:\/\/www.llu.edu\/ihi\/pedproto.pdf"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0094-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-009-0094-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0094-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T13:41:55Z","timestamp":1558705315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-009-0094-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,18]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["94"],"URL":"https:\/\/doi.org\/10.1007\/s00236-009-0094-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,18]]}}}