{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:52:05Z","timestamp":1694652725307},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2007,4]]},"abstract":"\n Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence\n A<\/jats:italic>\n is assigned a dimension dim(\n A<\/jats:italic>\n ) \u2208 [0,1] and a strong dimension Dim(\n A<\/jats:italic>\n ) \u2208 [0,1].\n <\/jats:p>\n \n Let DIM\n \u03b1<\/jats:sup>\n and DIM\n \u03b1<\/jats:sup>\n str<\/jats:sub>\n be the classes of all sequences of dimension \u03b1 and of strong dimension \u03b1, respectively. We show that DIM\n 0<\/jats:sup>\n is properly \u03a0\n 0<\/jats:sup>\n 2<\/jats:sub>\n , and that for all \u0394\n 0<\/jats:sup>\n 2<\/jats:sub>\n -computable \u03b1 \u2208 (0, 1], DIM\n \u03b1<\/jats:sup>\n is properly \u03a0\n 0<\/jats:sup>\n 3<\/jats:sub>\n .\n <\/jats:p>\n \n To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a coenumerable predicate is used rather than an enumerable predicate in the definition of the \u03a3\n 0<\/jats:sup>\n 1<\/jats:sub>\n level. For all \u0394\n 0<\/jats:sup>\n 2<\/jats:sub>\n -computable \u03b1 \u2208 [0, 1), we show that DIM\n \u03b1<\/jats:sup>\n str<\/jats:sub>\n is properly in the \u03a0\n 0<\/jats:sup>\n 3<\/jats:sub>\n level of this hierarchy. We show that DIM\n 1<\/jats:sup>\n str<\/jats:sub>\n is properly in the \u03a0\n 0<\/jats:sup>\n 2<\/jats:sub>\n level of this hierarchy.\n <\/jats:p>\n \n We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly \u03a0\n 0<\/jats:sup>\n 3<\/jats:sub>\n .\n <\/jats:p>","DOI":"10.1145\/1227839.1227845","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"13","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The arithmetical complexity of dimension and randomness"],"prefix":"10.1145","volume":"8","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[{"name":"University of Wyoming, Laramie, WY"}]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, IA"}]},{"given":"Sebastiaan A.","family":"Terwijn","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 16th IEEE Conference on Computational Complexity. 210--217","author":"Ambos-Spies K.","unstructured":"Ambos-Spies , K. , Merkle , W., Reimann , J. , and Stephan , F . 2001. Hausdorff dimension in exponential time . In Proceedings of the 16th IEEE Conference on Computational Complexity. 210--217 . Ambos-Spies, K., Merkle, W., Reimann, J., and Stephan, F. 2001. Hausdorff dimension in exponential time. In Proceedings of the 16th IEEE Conference on Computational Complexity. 210--217."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science. Springer Verlag. 632--643","author":"Athreya K. B.","unstructured":"Athreya , K. B. , Hitchcock , J. M., Lutz , J. H. , and Mayordomo , E . 2004. Effective strong dimension in algorithmic information and computational complexity . In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science. Springer Verlag. 632--643 . To appear in SIAM J. Comput. Athreya, K. B., Hitchcock, J. M., Lutz, J. H., and Mayordomo, E. 2004. Effective strong dimension in algorithmic information and computational complexity. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science. Springer Verlag. 632--643. To appear in SIAM J. Comput."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00244-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457179"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00340-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00138-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00454-4"},{"key":"e_1_2_1_10_1","volume-title":"Recursion Theory: Its Generalizations and Applications","author":"Jockusch C. G.","unstructured":"Jockusch , C. G. 1980. Degrees of generic sets . In Recursion Theory: Its Generalizations and Applications . London Mathematical Society Lecture Notes Series, vol. 45 . Cambridge University Press , New York. 110--139. Jockusch, C. G. 1980. Degrees of generic sets. In Recursion Theory: Its Generalizations and Applications. London Mathematical Society Lecture Notes Series, vol. 45. Cambridge University Press, New York. 110--139."},{"key":"e_1_2_1_11_1","volume-title":"Classical Descriptive Set Theory","author":"Kechris A. S.","unstructured":"Kechris , A. S. 1994. Classical Descriptive Set Theory . Springer Verlag . Kechris, A. S. 1994. Classical Descriptive Set Theory. Springer Verlag."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.4064\/fm-144-2-163-179","article-title":"Normal numbers and subsets of N with given densities","volume":"144","author":"Ki H.","year":"1994","unstructured":"Ki , H. and Linton , T. 1994 . Normal numbers and subsets of N with given densities . Fundamenta Mathematicae 144 , 163 -- 179 . Ki, H. and Linton, T. 1994. Normal numbers and subsets of N with given densities. Fundamenta Mathematicae 144, 163--179.","journal-title":"Fundamenta Mathematicae"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-37-1-265-285"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vit\u00e1nyi P. M. B. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd ed Springer Verlag Berlin. Li M. and Vit\u00e1nyi P. M. B. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd ed Springer Verlag Berlin.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00343-5"},{"key":"e_1_2_1_19_1","volume-title":"Descriptive Set Theory. North-Holland","author":"Moschovakis Y. N.","unstructured":"Moschovakis , Y. N. 1980. Descriptive Set Theory. North-Holland , Amsterdam . Moschovakis, Y. N. 1980. Descriptive Set Theory. North-Holland, Amsterdam."},{"key":"e_1_2_1_20_1","volume-title":"Studies in Logic and the Foundations of Mathematics","volume":"125","author":"Odifreddi P.","year":"1989","unstructured":"Odifreddi , P. 1989 . Classical recursion theory . In Studies in Logic and the Foundations of Mathematics , vol. 125 . North-Holland. Odifreddi, P. 1989. Classical recursion theory. In Studies in Logic and the Foundations of Mathematics, vol. 125. North-Holland."},{"key":"e_1_2_1_21_1","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers Jr","unstructured":"Rogers , Jr , H. 1967. Theory of Recursive Functions and Effective Computability . McGraw - Hill , New York . Rogers, Jr, H. 1967. Theory of Recursive Functions and Effective Computability. McGraw - Hill, New York."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Schnorr C. P. 1971. Zuf\u00e4lligkeit und wahrscheinlichkeit. Lecture Not. Math. 218. Schnorr C. P. 1971. Zuf\u00e4lligkeit und wahrscheinlichkeit. Lecture Not. Math. 218.","DOI":"10.1007\/BFb0112458"},{"key":"e_1_2_1_23_1","volume-title":"Basic Problems in Methodology and Linguistics","author":"Schnorr C. P.","unstructured":"Schnorr , C. P. 1977. A survey of the theory of random sequences . In Basic Problems in Methodology and Linguistics , R. E. Butts and J. Hintikka, Eds. D. Reidel . 193--211. Schnorr, C. P. 1977. A survey of the theory of random sequences. In Basic Problems in Methodology and Linguistics, R. E. Butts and J. Hintikka, Eds. D. Reidel. 193--211."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646509.694676"},{"key":"e_1_2_1_25_1","volume-title":"Finite Versus Infinite: Contributions to an Eternal Dilemma","author":"Staiger L.","unstructured":"Staiger , L. 2000. On the power of reading the whole infinite input tape . In Finite Versus Infinite: Contributions to an Eternal Dilemma , C. S. Calude and G. Paun, Eds. Springer Verlag . 335--348. Staiger, L. 2000. On the power of reading the whole infinite input tape. In Finite Versus Infinite: Contributions to an Eternal Dilemma, C. S. Calude and G. Paun, Eds. Springer Verlag. 335--348."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.023"},{"key":"e_1_2_1_27_1","unstructured":"Terwijn S. A. 2004. Complexity and randomness. Rendiconti del Seminario Matematico di Torino 62 1 1--38. Terwijn S. A. 2004. Complexity and randomness. Rendiconti del Seminario Matematico di Torino 62 1 1--38."},{"key":"e_1_2_1_29_1","volume-title":"\u00c9tude Critique de la Notion de Collectif. Gauthier Villars","author":"Ville J.","unstructured":"Ville , J. 1939. \u00c9tude Critique de la Notion de Collectif. Gauthier Villars , Paris . Ville, J. 1939. \u00c9tude Critique de la Notion de Collectif. Gauthier Villars, Paris."},{"key":"e_1_2_1_30_1","first-page":"714","article-title":"Degrees of complexity of subsets of the Baire space","volume":"19","author":"Wadge W. W.","year":"1972","unstructured":"Wadge , W. W. 1972 . Degrees of complexity of subsets of the Baire space . Not. Amer. Math. Soc. 19 , 714 -- 715 . Wadge, W. W. 1972. Degrees of complexity of subsets of the Baire space. Not. Amer. Math. Soc. 19, 714--715.","journal-title":"Not. Amer. Math. Soc."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227839.1227845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:15Z","timestamp":1672261755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227839.1227845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1227839.1227845"],"URL":"https:\/\/doi.org\/10.1145\/1227839.1227845","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
