{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T05:45:37Z","timestamp":1751521537458,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,12,12]],"date-time":"2016-12-12T00:00:00Z","timestamp":1481500800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Agence Nationale de la Recherche (FR)","award":["ANR-11-BS02-004"],"award-info":[{"award-number":["ANR-11-BS02-004"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00224-016-9739-4","type":"journal-article","created":{"date-parts":[[2016,12,12]],"date-time":"2016-12-12T00:54:27Z","timestamp":1481504067000},"page":"653-681","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Prediction of Infinite Words with Automata"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2259-069X","authenticated-orcid":false,"given":"Tim","family":"Smith","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,12]]},"reference":[{"key":"9739_CR1","doi-asserted-by":"publisher","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. In: Auer, P., Clark, A., Zeugmann, T., Zilles, S. (eds.) Algorithmic Learning Theory, Lecture Notes in Computer Science, vol. 8776, pp 125\u2013139. Springer International Publishing (2014). doi:\n                        10.1007\/978-3-319-11662-4_10","DOI":"10.1007\/978-3-319-11662-4_10"},{"issue":"3","key":"9739_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D Angluin","year":"1983","unstructured":"Angluin, D., Smith, C.H.: Inductive inference: Theory and methods. ACM Comput. Surv. 15(3), 237\u2013269 (1983). doi:\n                        10.1145\/356914.356918","journal-title":"ACM Comput. Surv."},{"key":"9739_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1017\/S0269964800003685","volume":"9","author":"D Blackwell","year":"1995","unstructured":"Blackwell, D.: Minimax vs. Bayes prediction. Probab. Eng. Inf. Sci. 9, 53\u201358 (1995). doi:\n                        10.1017\/S0269964800003685\n                        \n                    . \n                        http:\/\/journals.cambridge.org\/article_S0269964800003685","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9739_CR4","doi-asserted-by":"publisher","unstructured":"Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Inf. Control. 28(2), 125\u2013155 (1975). doi:\n                        10.1016\/S0019-9958(75)90261-2\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0019995875902612","DOI":"10.1016\/S0019-9958(75)90261-2"},{"key":"9739_CR5","doi-asserted-by":"crossref","unstructured":"Broglio, A., Liardet, P.: Predictions with Automata. In: Symbolic Dynamics and Its Applications, Contemporary Mathematics, vol. 135, pp 111\u2013124. American Mathematical Society (1992)","DOI":"10.1090\/conm\/135\/1185084"},{"key":"9739_CR6","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/3-540-46033-0_4","volume-title":"Artificial Evolution, Lecture Notes in Computer Science, vol. 2310","author":"U Cerruti","year":"2002","unstructured":"Cerruti, U., Giacobini, M., Liardet, P.: Prediction of binary sequences by evolving finite state machines. In: Collet, P., Fonlupt, C., Hao, J.K., Lutton, E., Schoenauer, M. (eds.) Artificial Evolution, Lecture Notes in Computer Science, vol. 2310, pp 42\u201353. Springer, Berlin (2002). doi:\n                        10.1007\/3-540-46033-0_4"},{"issue":"3","key":"9739_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2493252.2493257","volume":"5","author":"A Drucker","year":"2013","unstructured":"Drucker, A.: High-confidence predictions under adversarial uncertainty. TOCT 5(3), 12 (2013). doi:\n                        10.1145\/2493252.2493257","journal-title":"TOCT"},{"issue":"A6","key":"9739_CR8","first-page":"1","volume":"11B","author":"J Endrullis","year":"2010","unstructured":"Endrullis, J., Hendriks, D., Klop, J.W.: Degrees of Streams. Integers, Electron. J. Comb. Number Theory 11B(A6), 1\u201340 (2010). Proc.Leiden Numeration Conf","journal-title":"Integers, Electron. J. Comb. Number Theory"},{"key":"9739_CR9","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/18.144706","volume":"38","author":"M Feder","year":"1992","unstructured":"Feder, M., Merhav, N., Gutman, M.: Universal prediction of individual sequences. IEEE Trans. Inf. Theory 38, 1258\u20131270 (1992)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"9739_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/321386.321403","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14(2), 389\u2013418 (1967). doi:\n                        10.1145\/321386.321403","journal-title":"J. ACM"},{"issue":"5","key":"9739_CR11","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold, E.M.: Language identification in the limit. Inf. Control. 10(5), 447\u2013474 (1967). \n                        http:\/\/groups.lis.illinois.edu\/amag\/langev\/paper\/gold67limit.html","journal-title":"Inf. Control."},{"key":"9739_CR12","unstructured":"Hibbard, B.: Adversarial sequence prediction. In: Proceedings of the 2008 Conference on Artificial General Intelligence 2008: Proceedings of the First AGI Conference, pp. 399\u2013403. IOS Press, Amsterdam, The Netherlands, The Netherlands. \n                        http:\/\/dl.acm.org\/citation.cfm?id=1566174.1566212\n                        \n                     (2008)"},{"issue":"1-2","key":"9739_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2010.08.024","volume":"412","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M., Malcher, A.: Complexity of multi-head finite automata: Origins and directions. Theor. Comput. Sci. 412(1-2), 83\u201396 (2011). doi:\n                        10.1016\/j.tcs.2010.08.024","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9739_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF00290734","volume":"19","author":"J Hromkovi\u010d","year":"1983","unstructured":"Hromkovi\u010d, J.: One-way multihead deterministic finite automata. Acta Inform. 19(4), 377\u2013384 (1983). doi:\n                        10.1007\/BF00290734","journal-title":"Acta Inform."},{"issue":"3","key":"9739_CR15","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/BF01941135","volume":"28","author":"P Johansen","year":"1988","unstructured":"Johansen, P.: Inductive inference of ultimately periodic sequences. BIT Numer. Math. 28(3), 573\u2013580 (1988). doi:\n                        10.1007\/BF01941135","journal-title":"BIT Numer. Math."},{"key":"9739_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BFb0026598","volume-title":"Artificial Evolution, Lecture Notes in Computer Science, vol. 1363","author":"B Leblanc","year":"1998","unstructured":"Leblanc, B., Lutton, E., Allouche, J.P.: Inverse problems for finite automata: A solution based on genetic algorithms. In: Hao, J.K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) Artificial Evolution, Lecture Notes in Computer Science, vol. 1363, pp 157\u2013166. Springer, Berlin (1998). doi:\n                        10.1007\/BFb0026598"},{"key":"9739_CR17","doi-asserted-by":"publisher","unstructured":"Legg, S.: Is there an elegant universal theory of prediction?. In: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006, Proceedings, pp 274\u2013287 (2006). doi:\n                        10.1007\/11894841_23","DOI":"10.1007\/11894841_23"},{"key":"9739_CR18","unstructured":"Narendra, K.S., Thathachar, M.A.L.: Learning automata: an introduction. Prentice-hall, Inc., Upper Saddle River, NJ, USA (1989)"},{"issue":"3","key":"9739_CR19","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0022-0000(88) 90011-6","volume":"37","author":"MG O\u2019Connor","year":"1988","unstructured":"O\u2019Connor, M.G.: An unpredictability approach to finite-state randomness. J. Comput. Syst. Sci. 37(3), 324\u2013336 (1988). doi:\n                        10.1016\/0022-0000(88)90011-6","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9739_CR20","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0211030","volume":"11","author":"R Sedgewick","year":"1982","unstructured":"Sedgewick, R., Szymanski, T.G., Yao, A.C.: The complexity of finding cycles in periodic functions. SIAM J. Comput. 11(2), 376\u2013390 (1982). doi:\n                        10.1137\/0211030","journal-title":"SIAM J. Comput."},{"key":"9739_CR21","doi-asserted-by":"crossref","unstructured":"Shubert, B.: Games of Prediction of Periodic Sequences. Tech. rep., United States Naval Postgraduate School (1971)","DOI":"10.21236\/AD0733434"},{"key":"9739_CR22","doi-asserted-by":"publisher","unstructured":"Smith, T.: On Infinite Words Determined by Stack Automata. doi:\n                        10.4230\/LIPIcs.FSTTCS.2013.413\n                        \n                     (2013)","DOI":"10.4230\/LIPIcs.FSTTCS.2013.413"},{"key":"9739_CR23","volume-title":"Computer Science \u2014 Theory and Applications, CSR 2016","author":"T Smith","year":"2016","unstructured":"Smith, T.: Prediction of Infinite Words with Automata. In: Computer Science \u2014 Theory and Applications, CSR 2016. To appear. Springer, Berlin (2016)"},{"key":"9739_CR24","doi-asserted-by":"publisher","unstructured":"Solomonoff, R.: A formal theory of inductive inference. part i. Inf. Control. 7(1), 1\u201322 (1964). doi:\n                        10.1016\/S0019-9958(64)90223-2\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0019995864902232","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"9739_CR25","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Mathematics and its Applications Springer (1986)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9739-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9739-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9739-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T20:25:02Z","timestamp":1520972702000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9739-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,12]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9739"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9739-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,12,12]]}}}