{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:19Z","timestamp":1760202559748},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540730002"},{"type":"electronic","value":"9783540730019"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"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":[[2007]]},"DOI":"10.1007\/978-3-540-73001-9_24","type":"book-chapter","created":{"date-parts":[[2007,7,24]],"date-time":"2007-07-24T15:16:31Z","timestamp":1185290191000},"page":"228-237","source":"Crossref","is-referenced-by-count":8,"title":["Feasible Depth"],"prefix":"10.1007","author":[{"given":"David","family":"Doty","sequence":"first","affiliation":[]},{"given":"Philippe","family":"Moser","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"24_CR1","first-page":"391","volume":"354","author":"L. Antunes","year":"2006","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D., Vinodchandran, N.: Computational depth: Concept and applications. Theoretical Computer Science (Special issue for selected papers from the 14th International Symposium on Fundamentals of Computation Theory)\u00a0354(3), 391\u2013404 (2006)","journal-title":"Theoretical Computer Science (Special issue for selected papers from the 14th International Symposium on Fundamentals of Computation Theory)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/978-3-540-24749-4_55","volume-title":"STACS 2004","author":"K.B. Athreya","year":"2004","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension, algorithmic information, and computational complexity. SIAM Journal on Computing (to appear). Preliminary version appeared in: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 632\u2013643. Springer, Heidelberg (2004)"},{"key":"24_CR3","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"C.H. Bennett","year":"1988","unstructured":"Bennett, C.H.: Logical depth and physical complexity. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 227\u2013257. Oxford University Press, London (1988)"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF03019651","volume":"27","author":"E. Borel","year":"1909","unstructured":"Borel, E.: Sur les probabilit\u00e9s d\u00e9nombrables et leurs applications arithm\u00e9tiques. Rendiconti del Circolo Matematico di Palermo\u00a027, 247\u2013271 (1909)","journal-title":"Rendiconti del Circolo Matematico di Palermo"},{"key":"24_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, 392\u2013406 (to appear, 2005)","journal-title":"Theoretical Computer Science"},{"key":"24_CR6","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":"24_CR7","doi-asserted-by":"crossref","unstructured":"Doty, D., Moser, P.: Finite-state dimension and lossy decompressors. Technical Report cs.CC\/0609096, Computing Research Repository (2006)","DOI":"10.1007\/11786986_47"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.ic.2005.01.001","volume":"197","author":"S.A. Fenner","year":"2005","unstructured":"Fenner, S.A., Lutz, J.H., Mayordomo, E., Reardon, P.: Weakly useful sequences. Information and Computation\u00a0197, 41\u201354 (2005)","journal-title":"Information and Computation"},{"issue":"1\u20133","key":"24_CR9","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0304-3975(03)00138-5","volume":"304","author":"J.M. Hitchcock","year":"2003","unstructured":"Hitchcock, J.M.: Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science\u00a0304(1\u20133), 431\u2013441 (2003)","journal-title":"Theoretical Computer Science"},{"key":"24_CR10","unstructured":"Huffman, D.A.: Canonical forms for information-lossless finite-state logical machines. IRE Trans. Circuit Theory CT-6 (Special Supplement), pp. 41\u201359 (1959), Also available In: Moore, E.F. (ed.) Sequential Machine: Selected Papers, Addison-Wesley, pp. 866\u2013871 (1964)"},{"issue":"1\u20132","key":"24_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0304-3975(94)00014-X","volume":"132","author":"D.W. Juedes","year":"1994","unstructured":"Juedes, D.W., Lathrop, J.I., Lutz, J.H.: Computational depth and reducibility. Theoretical Computer Science\u00a0132(1\u20132), 37\u201370 (1994)","journal-title":"Theoretical Computer Science"},{"key":"24_CR12","volume-title":"Switching and Finite Automata Theory","author":"Z. Kohavi","year":"1978","unstructured":"Kohavi, Z.: Switching and Finite Automata Theory, 2nd edn. McGraw-Hill, New York (1978)","edition":"2"},{"issue":"2","key":"24_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/inco.1999.2794","volume":"153","author":"J.I. Lathrop","year":"1999","unstructured":"Lathrop, J.I., Lutz, J.H.: Recursive computational depth. Information and Computation\u00a0153(2), 139\u2013172 (1999)","journal-title":"Information and Computation"},{"key":"24_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997)","edition":"2"},{"issue":"2","key":"24_CR15","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci.\u00a044(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013254. Springer, Heidelberg (1997)"},{"key":"24_CR17","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":"24_CR18","doi-asserted-by":"crossref","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal, 27:379\u2013423, 623\u2013656 (1948)","DOI":"10.1002\/j.1538-7305.1948.tb00917.x"},{"issue":"1","key":"24_CR19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1006\/inco.1995.1009","volume":"116","author":"D. Sheinwald","year":"1995","unstructured":"Sheinwald, D., Lempel, A., Ziv, J.: On encoding and decoding with two-way head machines. Information and Computation\u00a0116(1), 128\u2013133 (1995)","journal-title":"Information and Computation"},{"key":"24_CR20","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 Transaction on Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Transaction on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Computation and Logic in the Real World"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73001-9_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T12:18:03Z","timestamp":1556713083000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73001-9_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540730002","9783540730019"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73001-9_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}