{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:00:58Z","timestamp":1725858058131},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319401881"},{"type":"electronic","value":"9783319401898"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-40189-8_15","type":"book-chapter","created":{"date-parts":[[2016,6,13]],"date-time":"2016-06-13T15:34:07Z","timestamp":1465832047000},"page":"142-152","source":"Crossref","is-referenced-by-count":1,"title":["Towards Computational Complexity Theory on Advanced Function Spaces in Analysis"],"prefix":"10.1007","author":[{"given":"Akitoshi","family":"Kawamura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Steinberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Ziegler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/978-3-540-74915-8_29","volume-title":"Computer Science Logic","author":"K Aehlig","year":"2007","unstructured":"Aehlig, K., Cook, S., Nguyen, P.: Relativizing small complexity classes and their theories. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 374\u2013388. Springer, Heidelberg (2007)"},{"issue":"3","key":"15_CR2","first-page":"318","volume":"53","author":"M Braverman","year":"2006","unstructured":"Braverman, M., Cook, S.A.: Computing over the reals: foundations for scientific computing. Not. AMS 53(3), 318\u2013329 (2006)","journal-title":"Not. AMS"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0022-0000(88)90034-7","volume":"36","author":"JF Buss","year":"1988","unstructured":"Buss, J.F.: Relativized alternation and space-bounded computation. J. Comput. Syst. Sci. 36, 351\u2013378 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"15_CR4","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.ic.2009.08.001","volume":"208","author":"M Brecht de","year":"2010","unstructured":"de Brecht, M., Yamamoto, A.: Topological properties of concept spaces. Inf. Comput. 208(4), 327\u2013340 (2010)","journal-title":"Inf. Comput."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Sankaranarayanan, S., Vardi, M.Y.: Regular real analysis. In: Proceedings of 28th Annual IEEE Symposium on Logic in Computer Science (LiCS2013), pp. 509\u2013518 (2013)","DOI":"10.1109\/LICS.2013.57"},{"key":"15_CR6","doi-asserted-by":"publisher","unstructured":"F\u00e9r\u00e9e, H., Ziegler, M.: On the Computational Complexity of Positive Linear Functionals on C[0;1]. In: Kotsireas, I.S., Rump, S.M., Yap, C.K. (eds.) MACIS 2015. LNCS, vol. 9582, pp. 489\u2013504. Springer, Heidelberg (2016). doi: 10.1007\/978-3-319-32859-1_42","DOI":"10.1007\/978-3-319-32859-1_42"},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2015.03.008","volume":"595","author":"H F\u00e9r\u00e9e","year":"2015","unstructured":"F\u00e9r\u00e9e, H., Hainry, E., Hoyrup, M., P\u00e9choux, R.: Characterizing polynomial time complexity of stream programs using interpretations. Theor. Comput. Sci. 595, 41\u201354 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR8","unstructured":"Gregoriades, V., Kihara, T.: Recursion and effectivity in the decomposability conjecture. (2014, submitted). arXiv:1410.1052"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.apal.2004.08.001","volume":"132","author":"P Hertling","year":"2004","unstructured":"Hertling, P.: A BanachMazur computable but not Markov computable function on the computable real numbers. Ann. Pure Appl. Log. 132, 227\u2013246 (2004)","journal-title":"Ann. Pure Appl. Log."},{"issue":"1","key":"15_CR10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/S0097539794263452","volume":"25","author":"BM Kapron","year":"1996","unstructured":"Kapron, B.M., Cook, S.A.: A new characterization of type-2 feasibility. SIAM J. Comput. 25(1), 117\u2013132 (1996)","journal-title":"SIAM J. Comput."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Kawamura, A., Cook, S.A.: Complexity theory for operators in analysis. In: Proceedings of 42nd Annual ACM Symposium on Theory of Computing (STOC 2010); Full Version in ACM Transactions in Computation Theory, vol. 4 no. 2, article 5 (2012)","DOI":"10.1145\/2189778.2189780"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1007\/978-3-662-44465-8_37","volume-title":"Mathematical Foundations of Computer Science 2014","author":"A Kawamura","year":"2014","unstructured":"Kawamura, A., Ota, H.: Small complexity classes for computable analysis. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 432\u2013444. Springer, Heidelberg (2014)"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/978-3-319-08019-2_25","volume-title":"Language, Life, Limits","author":"A Kawamura","year":"2014","unstructured":"Kawamura, A., Pauly, A.: Function spaces for second-order polynomial time. In: Beckmann, A., Csuhaj-Varj\u00fa, E., Meer, K. (eds.) CiE 2014. LNCS, vol. 8493, pp. 245\u2013254. Springer, Heidelberg (2014)"},{"issue":"5","key":"15_CR14","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/j.jco.2015.05.001","volume":"31","author":"A Kawamura","year":"2015","unstructured":"Kawamura, A., M\u00fcller, N., R\u00f6snick, C., Ziegler, M.: Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey\u2019s hierarchy. J. Complex. 31(5), 689\u2013714 (2015)","journal-title":"J. Complex."},{"key":"15_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Computational Complexity of Real Functions","author":"K-I Ko","year":"1991","unstructured":"Ko, K.-I.: Computational Complexity of Real Functions. Birkh\u00e4user, Boston (1991)"},{"key":"15_CR16","volume-title":"Applied Proof Theory","author":"U Kohlenbach","year":"2008","unstructured":"Kohlenbach, U.: Applied Proof Theory. Springer, Heidelberg (2008)"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1007\/978-3-642-32589-2_51","volume-title":"Mathematical Foundations of Computer Science 2012","author":"A Kawamura","year":"2012","unstructured":"Kawamura, A., Ota, H., R\u00f6snick, C., Ziegler, M.: Computational complexity of smooth differential equations. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 578\u2013589. Springer, Heidelberg (2012)"},{"issue":"2","key":"15_CR18","first-page":"3","volume":"14","author":"AN Kolmogorov","year":"1959","unstructured":"Kolmogorov, A.N., Tikhomirov, V.M.: $$\\cal {E}$$ E -Entropy and $${\\cal {E}}$$ E -Capacity of Sets in Functional Spaces. Uspekhi Mat. Nauk 14(2), 3\u201386 (1959). also pp. 86\u2013170 in Selected Works of A.N. Kolmogorov vol. III (Shiryayev, A.N. Ed.), Nauka (1993) and Springer (1987)","journal-title":"Uspekhi Mat. Nauk"},{"issue":"2","key":"15_CR19","first-page":"231","volume":"20","author":"A Kawamura","year":"2014","unstructured":"Kawamura, A., Steinberg, F., Ziegler, M.: Complexity of Laplace\u2019s and Poisson\u2019s Equation. Bulletin of Symbolic Logic 20(2), 231 (2014). Full version in Mathem. Structures in Computer Science (2016)","journal-title":"Bulletin of Symbolic Logic"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4115\/jla.2013.5.7","volume":"5","author":"A Pauly","year":"2013","unstructured":"Pauly, A., Ziegler, M.: Relative computability and uniform continuity of relations. J. Log. Anal. 5, 1\u201339 (2013)","journal-title":"J. Log. Anal."},{"key":"15_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21717-7","volume-title":"Computability in Analysis and Physics","author":"MB Pour-El","year":"1989","unstructured":"Pour-El, M.B., Richards, I.: Computability in Analysis and Physics. Springer, Heidelberg (1989)"},{"key":"15_CR22","unstructured":"Schr\u00f6der, M.: Topological spaces allowing type-2 complexity theory. In: Workshop on Computability and Complexity in Analysis, Informatik-Berichte 190, FernUniversit\u00e4t Hagen (1995)"},{"key":"15_CR23","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1002\/malq.200310111","volume":"50","author":"M Schr\u00f6der","year":"2004","unstructured":"Schr\u00f6der, M.: Spaces allowing type-2 complexity theory revisited. Math. Logic Q. 50, 443\u2013459 (2004)","journal-title":"Math. Logic Q."},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/11780342_48","volume-title":"Logical Approaches to Computational Barriers","author":"M Schr\u00f6der","year":"2006","unstructured":"Schr\u00f6der, M.: Admissible representations in computable analysis. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol. 3988, pp. 471\u2013480. Springer, Heidelberg (2006)"},{"key":"15_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-319-20028-6_34","volume-title":"Evolving Computability","author":"SM Sun","year":"2015","unstructured":"Sun, S.M., Zhong, N., Ziegler, M.: On the Computability of the Navier-Stokes Equation. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) Evolving Computability. LNCS, vol. 9136, pp. 334\u2013342. Springer, Heidelberg (2015)"},{"key":"15_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis","author":"K Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis. Springer, Heidelberg (2000)"},{"issue":"1","key":"15_CR27","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/malq.200310001","volume":"49","author":"K Weihrauch","year":"2003","unstructured":"Weihrauch, K.: Computational complexity on computable metric spaces. Math. Log. Q. 49(1), 3\u201321 (2003)","journal-title":"Math. Log. Q."},{"issue":"2","key":"15_CR28","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1112\/S0024611502013643","volume":"85","author":"K Weihrauch","year":"2002","unstructured":"Weihrauch, K., Zhong, N.: Is wave propagation computable or can wave computers beat the turing machine? Proc. London Math. Soc. 85(2), 312\u2013332 (2002)","journal-title":"Proc. London Math. Soc."},{"key":"15_CR29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-0000(88)90031-1","volume":"36","author":"CB Wilson","year":"1988","unstructured":"Wilson, C.B.: A measure of relativized space which is faithful with respect to depth. J. Comput. Syst. Sci. 36, 303\u2013312 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR30","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00224-006-1343-6","volume":"41","author":"M Ziegler","year":"2007","unstructured":"Ziegler, M.: Real hypercomputation and continuity. Theory Comput. Syst. 41, 177\u2013206 (2007)","journal-title":"Theory Comput. Syst."}],"container-title":["Lecture Notes in Computer Science","Pursuit of the Universal"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40189-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T16:17:30Z","timestamp":1498321050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40189-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319401881","9783319401898"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40189-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}