{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T08:16:13Z","timestamp":1770884173753,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662557501","type":"print"},{"value":"9783662557518","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-662-55751-8_33","type":"book-chapter","created":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T15:32:49Z","timestamp":1502811169000},"page":"418-430","source":"Crossref","is-referenced-by-count":5,"title":["Automatic Kolmogorov Complexity and Normality Revisited"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Shen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"key":"33_CR1","first-page":"255","volume":"179","author":"VN Agafonov","year":"1968","unstructured":"Agafonov, V.N.: Normal sequences and finite automata. Doklady AN SSSR 179, 255\u2013256 (1968). See also the paper of V.N. Agafonov with the same name: Problemy Kibernetiki. vol. 20, pp. 123\u2013129. Nauka, Moscow (1968)","journal-title":"Doklady AN SSSR"},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-30870-3_5","volume-title":"How the World Computes","author":"V Becher","year":"2012","unstructured":"Becher, V.: Turing\u2019s normal numbers: towards randomness. In: Cooper, S.B., Dawar, A., L\u00f6we, B. (eds.) CiE 2012. LNCS, vol. 7318, pp. 35\u201345. Springer, Heidelberg (2012). doi:\n10.1007\/978-3-642-30870-3_5"},{"key":"33_CR3","unstructured":"Becher, V., Carton, O., Heiber, P.: Finite-state independence, 12 November 2016. \nhttps:\/\/arxiv.org\/pdf\/1611.03921.pdf"},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.tcs.2013.01.019","volume":"477","author":"V Becher","year":"2013","unstructured":"Becher, V., Heiber, P.: Normal number and finite automata. Theoret. Comput. Sci. 477, 109\u2013116 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR5","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Vieweg+Teubner Verlag, Wiesbaden (1969). For a revised 2006\u20132009 version see the author\u2019s homepage. ISBN 978-3-519-02340-1. \nhttp:\/\/www-igm.univ-mlv.fr\/~berstel"},{"key":"33_CR6","series-title":"Cambridge Tracts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139017732","volume-title":"Distribution Modulo One and Diophantine Approximation","author":"Y Bugeaud","year":"2012","unstructured":"Bugeaud, Y.: Distribution Modulo One and Diophantine Approximation. Cambridge Tracts in Mathematics, vol. 193. Cambridge University Press, Cambridge (2012)"},{"issue":"4","key":"33_CR7","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1112\/jlms\/s1-8.4.254","volume":"8","author":"D Champernowne","year":"1933","unstructured":"Champernowne, D.: The construction of decimals normal in the scale of ten. J. London Math. Soc. 8(4), 254\u2013260 (1933). (Received 19 April, read 27 April 1933)","journal-title":"J. London Math. Soc."},{"key":"33_CR8","doi-asserted-by":"crossref","first-page":"5668","DOI":"10.1016\/j.tcs.2011.06.021","volume":"412","author":"CS Calude","year":"2011","unstructured":"Calude, C.S., Salomaa, K., Roblot, T.K.: Finite state complexity. Theoret. Comput. Sci. 412, 5668\u20135677 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Hirschfeldt, D.R.: Algorithimic Randomness and Complexity, xxviii+855 p. Springer, New York (2010). ISBN 978-0-387-68441-3","DOI":"10.1007\/978-0-387-68441-3"},{"key":"33_CR10","first-page":"3","volume":"22","author":"KK Hyde","year":"2015","unstructured":"Hyde, K.K., Kjos-Hanssen, B.: Nondeterministic complexity of overlap-free and almost square-free words. Electron. J. Comb. 22, 3 (2015)","journal-title":"Electron. J. Comb."},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, pp. 1\u2013792. Springer, New York (2008). ISBN 978-0-387-49820-1","edition":"3"},{"key":"33_CR12","volume-title":"Uniform Distribution of Sequences","author":"L Kuipers","year":"1974","unstructured":"Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley, Hoboken (1974)"},{"key":"33_CR13","series-title":"Oxford Logic Guides","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001","volume-title":"Computability and Randomness","author":"A Nies","year":"2009","unstructured":"Nies, A.: Computability and Randomness. Oxford Logic Guides. Oxford University Press, Oxford (2009). ISBN 978-0199652600"},{"issue":"4","key":"33_CR14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00289514","volume":"1","author":"C Schnorr","year":"1972","unstructured":"Schnorr, C., Stimm, H.: Endliche Automaten und Zufallsfolgen. Acta Informatica 1(4), 345\u2013359 (1972)","journal-title":"Acta Informatica"},{"issue":"4","key":"33_CR15","first-page":"537","volume":"6","author":"J Shallit","year":"2001","unstructured":"Shallit, J., Wang, M.-W.: Automatic complexity of strings. J. Automata Lang. Comb. 6(4), 537\u2013554 (2001)","journal-title":"J. Automata Lang. Comb."},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-319-21852-6_7","volume-title":"Measures of Complexity","author":"A Shen","year":"2015","unstructured":"Shen, A.: Around Kolmogorov complexity: basic notions and results. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity, pp. 75\u2013115. Springer, Cham (2015). doi:\n10.1007\/978-3-319-21852-6_7\n\n. see also \nhttp:\/\/arxiv.org\/abs\/1504.04955"},{"key":"33_CR17","unstructured":"Shen, A., Uspensky, V.A., Vereshchagin, N.: Kolmogorov Complexity and Algorithmic Randomness. MCCME, Moscow (2013). (in Russian), English version accepted for publication by AMS. \nwww.lirmm.fr\/ashen\/kolmbook-eng.pdf"},{"issue":"1","key":"33_CR18","first-page":"47","volume":"15","author":"II Piatetski-Shapiro","year":"1951","unstructured":"Piatetski-Shapiro, I.I.: On the laws of distribution of the fractional parts of an exponential function. Izvestia Akademii Nauk SSSR Seriya Matematicheskaya 15(1), 47\u201352 (1951). (in Russian)","journal-title":"Izvestia Akademii Nauk SSSR Seriya Matematicheskaya"},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF01201280","volume":"29","author":"VA Uspensky","year":"1996","unstructured":"Uspensky, V.A., Shen, A.: Relations between varieties of Kolmogorov complexities. Math. Syst. Theory 29, 271\u2013292 (1996)","journal-title":"Math. Syst. Theory"},{"key":"33_CR20","unstructured":"Wall, D.D.: Normal numbers. Thesis, University of California (1949)"},{"issue":"8","key":"33_CR21","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/BF00264285","volume":"27","author":"A Weber","year":"1990","unstructured":"Weber, A.: On the valuedness of finite transducers. Acta Informatica 27(8), 749\u2013780 (1990)","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-55751-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T15:41:56Z","timestamp":1502811716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-55751-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662557501","9783662557518"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-55751-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}