{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T10:29:56Z","timestamp":1725791396315},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319060880"},{"type":"electronic","value":"9783319060897"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06089-7_5","type":"book-chapter","created":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T01:55:10Z","timestamp":1396317310000},"page":"50-66","source":"Crossref","is-referenced-by-count":0,"title":["Finite State Incompressible Infinite Sequences"],"prefix":"10.1007","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ludwig","family":"Staiger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","first-page":"324","volume":"9","author":"V.N. Agafonov","year":"1968","unstructured":"Agafonov, V.N.: Normal sequences and finite automata. Soviet Mathematics Doklady\u00a09, 324\u2013325 (1968)","journal-title":"Soviet Mathematics Doklady"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-45066-1_7","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"K. Ambos-Spies","year":"2003","unstructured":"Ambos-Spies, K., Busse, E.: Automatic forcing and genericity: On the diagonalization strength of finite automata. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol.\u00a02731, pp. 97\u2013108. Springer, Heidelberg (2003)"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/978-3-540-28629-5_55","volume-title":"Mathematical Foundations of Computer Science 2004","author":"K. Ambos-Spies","year":"2004","unstructured":"Ambos-Spies, K., Busse, E.: Computational aspects of disjunctive sequences. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 711\u2013722. Springer, Heidelberg (2004)"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-free Languages. Teubner (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1016\/j.tcs.2005.09.040","volume":"349","author":"C. Bourke","year":"2005","unstructured":"Bourke, C., Hitchcock, J.M., Vinodchandran, N.V.: Entropy rates and finite-state dimension. Theoretical Computer Science\u00a0349(3), 392\u2013406 (2005)","journal-title":"Theoretical Computer Science"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BFb0023452","volume-title":"STACS 97","author":"H. Buhrman","year":"1997","unstructured":"Buhrman, H., Fortnow, L.: Resource-bounded Kolmogorov complexity revisited. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 105\u2013116. Springer, Heidelberg (1997)"},{"key":"5_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5","volume-title":"Information and Randomness. An Algorithmic Perspective","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S.: Information and Randomness. An Algorithmic Perspective, 2nd edn. Springer, Berlin (2002)","edition":"2"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1016\/j.jcss.2010.08.001","volume":"77","author":"C.S. Calude","year":"2011","unstructured":"Calude, C.S., Hay, N.J., Stephan, F.: Representation of left-computable \u03b5\u2013random reals. Journal of Computer and System Sciences\u00a077, 812\u2013839 (2011)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"5668","DOI":"10.1016\/j.tcs.2011.06.021","volume":"412","author":"C.S. Calude","year":"2011","unstructured":"Calude, C.S., Salomaa, K., Roblot, T.K.: Finite state complexity. Theoretical Computer Science\u00a0412, 5668\u20135677 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1142\/S0129054112400035","volume":"25","author":"C.S. Calude","year":"2012","unstructured":"Calude, C.S., Salomaa, K., Roblot, T.K.: State-size hierarchy for FS-complexity. International Journal of Foundations of Computer Science\u00a025(1), 37\u201350 (2012)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G.J. Chaitin","year":"1975","unstructured":"Chaitin, G.J.: A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery\u00a022, 329\u2013340 (1975)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1112\/jlms\/s1-8.4.254","volume":"8","author":"D.G. Champernowne","year":"1933","unstructured":"Champernowne, D.G.: The construction of decimals normal in the scale of ten. Journal of the London Mathematical Society\u00a08, 254\u2013260 (1933)","journal-title":"Journal of the London Mathematical Society"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the smallest grammar: Kolmogorov complexity in natural models. In: Proceedings of STOC 2002, pp. 792\u2013801. ACM Press (2002)","DOI":"10.1145\/510019.510021"},{"key":"5_CR14","first-page":"758","volume":"49","author":"N. Bruijn de","year":"1946","unstructured":"de Bruijn, N.: A combinatorial problem. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen\u00a049, 758\u2013764 (1946)","journal-title":"Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(03)00244-5","volume":"310","author":"J.J. Dai","year":"2004","unstructured":"Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theoretical Computer Science\u00a0310, 1\u201333 (2004)","journal-title":"Theoretical Computer Science"},{"key":"5_CR16","unstructured":"Doty, D., Moser, P.: Finite-state dimension and lossy compressors, arxiv:cs\/0609096v2 (2006)"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73001-9_24","volume-title":"Computation and Logic in the Real World","author":"D. Doty","year":"2007","unstructured":"Doty, D., Moser, P.: Feasible Depth. In: Cooper, S.B., L\u00f6we, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol.\u00a04497, pp. 228\u2013237. Springer, Heidelberg (2007)"},{"key":"5_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic Randomness and Complexity","author":"R. Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Heidelberg (2010)"},{"issue":"3","key":"5_CR19","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/S0019-9958(78)90062-1","volume":"38","author":"H.P. Katseff","year":"1978","unstructured":"Katseff, H.P.: Complexity dips in random infinite binary sequences. Information and Control\u00a038(3), 258\u2013263 (1978)","journal-title":"Information and Control"},{"key":"5_CR20","unstructured":"Lehman, E.: Approximation Algorithms for Grammar-based Compression, PhD Thesis. MIT (2002)"},{"key":"5_CR21","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: Proceedings of SODA 2002, pp. 205\u2013212. SIAM Press (2002)"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer (2007)","DOI":"10.1007\/978-0-387-49820-1"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information and Control\u00a09, 602\u2013619 (1966)","journal-title":"Information and Control"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"Martin-L\u00f6f, P.: Complexity oscillations in infinite binary sequences. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete\u00a019, 225\u2013230 (1971)","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete"},{"key":"5_CR25","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001","volume-title":"Computability and Randomness","author":"A. Nies","year":"2009","unstructured":"Nies, A.: Computability and Randomness. Clarendon Press, Oxford (2009)"},{"key":"5_CR26","unstructured":"Nandakumar, S., Vangapelli, S.K.: Normality and finite-state dimension of Liouville numbers, arxiv:1204.4104v1 [cs.IT] (2012)"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2002","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Science\u00a0302, 211\u2013222 (2002)","journal-title":"Theoretical Computer Science"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00289514","volume":"1","author":"C.P. Schnorr","year":"1972","unstructured":"Schnorr, C.P., Stimm, H.: Endliche Automaten und Zufallsfolgen. Acta Informatica\u00a01, 345\u2013359 (1972)","journal-title":"Acta Informatica"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C.P. Schnorr","year":"1973","unstructured":"Schnorr, C.P.: Process complexity and effective randomness tests. Journal of Comput. System Sciences\u00a07, 376\u2013388 (1973)","journal-title":"Journal of Comput. System Sciences"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0304-3975(01)00102-5","volume":"284","author":"L. Staiger","year":"2002","unstructured":"Staiger, L.: The Kolmogorov complexity of real numbers. Theoretical Computer Science\u00a0284, 455\u2013466 (2002)","journal-title":"Theoretical Computer Science"},{"key":"5_CR31","unstructured":"Tadaki, K.: Phase Transition and Strong Predictability, CDMTCS Research Report 435 (2013)"},{"key":"5_CR32","unstructured":"van Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press (1993)"},{"key":"5_CR33","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06089-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T13:23:42Z","timestamp":1648733022000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06089-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319060880","9783319060897"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06089-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}