{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:26Z","timestamp":1725665006320},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540628446"},{"type":"electronic","value":"9783540687030"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62844-4_26","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:50:55Z","timestamp":1330296655000},"page":"366-376","source":"Crossref","is-referenced-by-count":2,"title":["Two lower bounds on computational complexity of infinite words"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/BF00289160","volume":"26","author":"J. M. Autebert","year":"1989","unstructured":"J. M. Autebert, J. Gabarr\u00f3: Iterated GSM's and Co-CFL. Acta Informatica 26(1989), 749\u2013769.","journal-title":"Acta Informatica"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"K. Culik II, and J. Karhum\u00e4ki: Iterative devices generating infinite words. In: Lecture Notes in Computer Science 577, Springer-Verlag 1992. (also Int. J. Found. Comput. Sci. 5 (1994), 69\u201397).","DOI":"10.1142\/S0129054194000050"},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/321495.321506","volume":"16","author":"G. J. Chaitin","year":"1969","unstructured":"G. J. Chaitin: On the length of programs for computing finite binary sequences: statistical considerations. J. Assoc. Comp. Mach. 16 (1969), 145\u2013159.","journal-title":"J. Assoc. Comp. Mach."},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/S0022-0000(70)80012-5","volume":"4","author":"P. C. Fischer","year":"1970","unstructured":"P. C. Fischer, A. Meyer, and A. Rosenberg: Time restricted sequence generation. J. Comp. Syst. Sci. 4 (1970), 50\u201373.","journal-title":"J. Comp. Syst. Sci."},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, J. Karkum\u00e4ki, A. Lepist\u00f6: Computational complexity of infinite word generation. In: \u201cResults and Trends in Theoretical Computer Science\u201d (H. Maurer, ed.), Lecture Notes in Computer Science 812, Springer Verlag 1994, 169\u2013182.","DOI":"10.1007\/3-540-58131-6_46"},{"key":"26_CR6","unstructured":"J. E. Hopcroft, J. D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, Inc. 1979."},{"key":"26_CR7","first-page":"662","volume":"1","author":"A. N. Kolmogorov","year":"1968","unstructured":"A. N. Kolmogorov: Three approaches to the quantitative definition of information. Problems Inform. Transmission 1(1968), 662\u2013664.","journal-title":"Problems Inform. Transmission"},{"key":"26_CR8","first-page":"187","volume-title":"Handbook of Theoretical Computer Science A \u2014 Algorithms and Complexity","author":"M. Li","year":"1990","unstructured":"M. Li, P. M. B. Vit\u00e1nyi: Kolmogorov complexity and its applications. In: Handbook of Theoretical Computer Science A \u2014 Algorithms and Complexity (Jan van Leeuwen, ed.), Elsevier, Amsterdam, New York-Oxford-Tokyo & The MIT Press, Cambridge 1990, 187\u2013254."},{"key":"26_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1993","unstructured":"M. Li, P. M. B. Vit\u00e1nyi: An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 1993."},{"key":"26_CR10","first-page":"350","volume-title":"Developments in Language Theory II","author":"A. Lepist\u00f6","year":"1996","unstructured":"A. Lepist\u00f6: On the computational complexity of infinite words. In: Developments in Language Theory II (J. Dassow, G. Rozenberg, and A. Salomaa, eds.), World-Scientific, Singapore, 1996, 350\u2013359."},{"key":"26_CR11","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1981","unstructured":"M. Lothaire: Combinatorics on Words. Addison-Wesley, Reading, Massachusetts 1981."},{"key":"26_CR12","volume-title":"Jewels of Formal Language Theory","author":"A. Salomaa","year":"1981","unstructured":"A. Salomaa: Jewels of Formal Language Theory. Computer Science Press, Rockville, Maryland 1981."},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. J. Solomonoff","year":"1964","unstructured":"R. J. Solomonoff: A formal theory of inductive inference. Part 1 and Part 2. Inform. and Control 7(1964), 1\u201322 and 224\u2013254.","journal-title":"Inform. and Control"},{"key":"26_CR14","first-page":"1","volume":"7","author":"A. Thue","year":"1906","unstructured":"A. Thue: \u00dcber unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I Mat. Nat. KI., Kristiania 7 (1906), 1\u201322.","journal-title":"Norske Vid. Selsk. Skr., I Mat. Nat. KI., Kristiania"}],"container-title":["Lecture Notes in Computer Science","New Trends in Formal Languages"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62844-4_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:22Z","timestamp":1605647662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62844-4_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540628446","9783540687030"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-62844-4_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}