{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:55Z","timestamp":1740109375751,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00224-022-10094-9","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T04:02:36Z","timestamp":1661832156000},"page":"491-520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ergodic Theorems and Converses for PSPACE Functions"],"prefix":"10.1007","volume":"67","author":[{"given":"Satyadev","family":"Nandakumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8426-4326","authenticated-orcid":false,"given":"Subin","family":"Pulari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"key":"10094_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.ic.2011.10.006","volume":"210","author":"L Bienvenu","year":"2012","unstructured":"Bienvenu, L., Day, A., Hoyrup, M., Mezhirov, I., Shen, A.: A constructive version of Birkhoff\u2019s ergodic theorem for martin-l\u00f6f random points. Inf. Comput. 210, 21\u201330 (2012)","journal-title":"Inf. Comput."},{"key":"10094_CR2","volume-title":"Probability and Measure","author":"P Billingsley","year":"1986","unstructured":"Billingsley, P.: Probability and Measure, second edn. Wiley, New York (1986)","edition":"second edn."},{"key":"10094_CR3","volume-title":"Foundations of Constructive Analysis","author":"E Bishop","year":"1967","unstructured":"Bishop, E.: Foundations of Constructive Analysis. McGraw-Hill, New York (1967)"},{"key":"10094_CR4","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Hirschfeldt, D.R.: Algorithmic randomness and complexity. Springer Science & Business Media (2010)","DOI":"10.1007\/978-0-387-68441-3"},{"key":"10094_CR5","doi-asserted-by":"publisher","first-page":"711","DOI":"10.17323\/1609-4514-2014-14-4-711-744","volume":"14","author":"JN Franklin","year":"2014","unstructured":"Franklin, J.N., Towsner, H.: Randomness and non-ergodic systems. Moscow Math. J. 14, 711\u2013744 (2014)","journal-title":"Moscow Math. J."},{"issue":"21-23","key":"10094_CR6","doi-asserted-by":"publisher","first-page":"2207","DOI":"10.1016\/j.tcs.2009.02.010","volume":"410","author":"S Galatolo","year":"2009","unstructured":"Galatolo, S., Hoyrup, M., Rojas, C.: A constructive borel\u2013Cantelli lemma. Constructing orbits with required statistical properties. Theor. Comput. Sci. 410(21-23), 2207\u20132222 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"10094_CR7","doi-asserted-by":"crossref","unstructured":"Galotolo, S., Hoyrup, M., Rojas, C.: Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems. In: 7th International conference on computability and complexity in analysis, pp. 7\u201318 (2010)","DOI":"10.4204\/EPTCS.24.6"},{"issue":"6","key":"10094_CR8","doi-asserted-by":"publisher","first-page":"2135","DOI":"10.1214\/09-AOP460","volume":"37","author":"M Hochman","year":"2009","unstructured":"Hochman, M.: Upcrossing ineualities for stationary sequences and applications. Ann. Probab. 37(6), 2135\u20132149 (2009)","journal-title":"Ann. Probab."},{"key":"10094_CR9","unstructured":"Hoyrup, M.: The dimension of ergodic random sequences. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 567\u2013576 (2012)"},{"key":"10094_CR10","doi-asserted-by":"crossref","unstructured":"Hoyrup, M., Rojas, C.: Applications of effective probability theory to Martin-L\u00f6f randomness. In: International colloquium on automata, languages, and programming, pp. 549\u2013561. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_46"},{"issue":"7","key":"10094_CR11","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1016\/j.ic.2008.12.009","volume":"207","author":"M Hoyrup","year":"2009","unstructured":"Hoyrup, M., Rojas, C.: Computability of probability measures and martin-l\u00f6f randomness over metric spaces. Inf. Comput. 207(7), 830\u2013847 (2009)","journal-title":"Inf. Comput."},{"key":"10094_CR12","unstructured":"Huang, X., Stull, D.M.: Polynomial space randomness in analysis. In: MFCS (2016)"},{"key":"10094_CR13","unstructured":"Ko, K.I.: Complexity theory of real functions. Springer Science & Business Media (2012)"},{"key":"10094_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01300052","volume":"86","author":"U Krengel","year":"1978","unstructured":"Krengel, U.: On the speed of convergence in the ergodic theorem. Monatshefte F\u00fcr Mathematik 86, 3\u20136 (1978)","journal-title":"Monatshefte F\u00fcr Mathematik"},{"key":"10094_CR15","volume-title":"Uniform Distribution of Sequences","author":"L Kuipers","year":"1974","unstructured":"Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley-Interscience, New York (1974). Pure and Applied Mathematics"},{"key":"10094_CR16","unstructured":"van Lambalgen, M.: Random sequences. Ph.D. thesis, Department of Mathematics University of Amsterdam (1987)"},{"issue":"1","key":"10094_CR17","doi-asserted-by":"publisher","first-page":"23","DOI":"10.2140\/pjm.1952.2.23","volume":"2","author":"JE Maxfield","year":"1952","unstructured":"Maxfield, J.E.: A short proof of Pillai\u2019s theorem on normal numbers. Pac. J. Math. 2(1), 23\u201324 (1952)","journal-title":"Pac. J. Math."},{"key":"10094_CR18","doi-asserted-by":"crossref","unstructured":"Nandakumar, S.: An effective ergodic theorem and some applications. In: Proceedings of the 40th Annual Symposium on the Theory of Computing, pp. 39\u201344 (2008)","DOI":"10.1145\/1374376.1374383"},{"key":"10094_CR19","doi-asserted-by":"crossref","unstructured":"Nandakumar, S., Pulari, S., Vishnoi, P., Viswanathan, G.: An analogue of Pillai\u2019s theorem for continued fraction normality and an application to subsequences Bulletin of the London Mathematical Society (2021)","DOI":"10.1112\/blms.12507"},{"key":"10094_CR20","doi-asserted-by":"crossref","unstructured":"Nies, A.: Computability and randomness, vol. 51 OUP Oxford (2009)","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"10094_CR21","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF03049088","volume":"11","author":"SS Pillai","year":"1940","unstructured":"Pillai, S.S.: On normal numbers. Proc. Ind. Acad. Sci. Sect. A 11, 73\u201380 (1940)","journal-title":"Proc. Ind. Acad. Sci. Sect. A"},{"key":"10094_CR22","unstructured":"Rute, J.: Topics in algorithmic randomness and computable analysis. Ph.D. thesis, Carnegie Mellon University (2013)"},{"key":"10094_CR23","unstructured":"Stull, D.M.: Algorithmic randomness and analysis. Ph.D. thesis, Iowa State University, Ames, Iowa USA (2017)"},{"key":"10094_CR24","first-page":"301","volume":"50","author":"DM Stull","year":"2020","unstructured":"Stull, D.M.: Resource bounded randomness and its applications. Alg. Random. Prog. Prospects 50, 301 (2020)","journal-title":"Alg. Random. Prog. Prospects"},{"issue":"3","key":"10094_CR25","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/1132061","volume":"32","author":"VG Vovk","year":"1988","unstructured":"Vovk, V.G.: The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences. Theory Probab. its Appl. 32(3), 413\u2013425 (1988)","journal-title":"Theory Probab. its Appl."},{"issue":"1","key":"10094_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1137\/S0040585X97975915","volume":"42","author":"VV V\u2019yugin","year":"1997","unstructured":"V\u2019yugin, V.V.: Effective convergence in probability and an ergodic theorem for individual random sequences. Theory Probab. its Appl. 42(1), 39\u201350 (1997)","journal-title":"Theory Probab. its Appl."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10094-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10094-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10094-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T01:03:31Z","timestamp":1688605411000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10094-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,30]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10094"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10094-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,8,30]]},"assertion":[{"value":"14 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}