{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T14:16:19Z","timestamp":1725804979803},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319108810"},{"type":"electronic","value":"9783319108827"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10882-7_7","type":"book-chapter","created":{"date-parts":[[2014,9,11]],"date-time":"2014-09-11T02:54:19Z","timestamp":1410404059000},"page":"97-114","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic Recursion Theory and Implicit Computational Complexity"],"prefix":"10.1007","author":[{"given":"Ugo","family":"Dal Lago","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sara","family":"Zuppiroli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"7_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the polytime functions. Computational Complexity\u00a02(2), 97\u2013110 (1992)","journal-title":"Computational Complexity"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Foundations and Trends in Theoretical Computer Science\u00a02(1) (2006)","DOI":"10.1561\/0400000004"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-32495-6_1","volume-title":"Foundational and Practical Aspects of Resource Analysis","author":"U. Dal Lago","year":"2012","unstructured":"Dal Lago, U., Parisen Toldin, P.: A higher-order characterization of probabilistic polynomial time. In: Pe\u00f1a, R., van Eekelen, M., Shkaravska, O. (eds.) FOPARA 2011. LNCS, vol.\u00a07177, pp. 1\u201318. Springer, Heidelberg (2012)"},{"key":"7_CR4","unstructured":"Dal Lago, U., Zuppiroli, S.: Probabilistic recursion theory and implicit computational complexity (long version) (2014), http:\/\/arxiv.org\/abs\/1406.3378"},{"key":"7_CR5","first-page":"183","volume":"34","author":"K. Leeuw De","year":"1956","unstructured":"De Leeuw, K., Moore, E.F., Shannon, C.E., Shapiro, N.: Computability by probabilistic machines. Automata Studies\u00a034, 183\u2013198 (1956)","journal-title":"Automata Studies"},{"issue":"4","key":"7_CR6","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM Journal on Computing\u00a06(4), 675\u2013695 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1006\/inco.1998.2700","volume":"143","author":"J.-Y. Girard","year":"1998","unstructured":"Girard, J.-Y.: Light linear logic. Inf. Comput.\u00a0143(2), 175\u2013204 (1998)","journal-title":"Inf. Comput."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press (2000)","DOI":"10.1017\/CBO9780511546891"},{"issue":"2","key":"7_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences\u00a028(2), 270\u2013299 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR10","unstructured":"Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman & Hall\/Crc Cryptography and Network Security Series. Chapman & Hall\/CRC (2007)"},{"issue":"1","key":"7_CR11","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/BF01565439","volume":"112","author":"S.C. Kleene","year":"1936","unstructured":"Kleene, S.C.: General recursive functions of natural numbers. Mathematische Annalen\u00a0112(1), 727\u2013742 (1936)","journal-title":"Mathematische Annalen"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Leivant, D.: Ramified recurrence and computational complexity I: Word recurrence and poly-time. In: Feasible Mathematics II, pp. 320\u2013343. Springer (1995)","DOI":"10.1007\/978-1-4612-2566-9_11"},{"issue":"1\/2","key":"7_CR13","doi-asserted-by":"crossref","first-page":"167","DOI":"10.3233\/FI-1993-191-207","volume":"19","author":"D. Leivant","year":"1993","unstructured":"Leivant, D., Marion, J.-Y.: Lambda calculus characterizations of poly-time. Fundam. Inform.\u00a019(1\/2), 167\u2013184 (1993)","journal-title":"Fundam. Inform."},{"issue":"3","key":"7_CR14","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Information and Control\u00a06(3), 230\u2013245 (1963)","journal-title":"Information and Control"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev.\u00a03(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"7_CR16","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1090\/S0002-9939-1969-0249221-4","volume":"22","author":"E.S. Santos","year":"1969","unstructured":"Santos, E.S.: Probabilistic Turing machines and computability. Proceedings of the American Mathematical Society\u00a022(3), 704\u2013710 (1969)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1090\/S0002-9947-1971-0281555-3","volume":"159","author":"E.S. Santos","year":"1971","unstructured":"Santos, E.S.: Computability by probabilistic turing machines. Transactions of the American Mathematical Society\u00a0159, 165\u2013184 (1971)","journal-title":"Transactions of the American Mathematical Society"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Soare, R.I.: Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Perspectives in mathematical logic. Springer (1987)","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10882-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T17:19:11Z","timestamp":1650129551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10882-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319108810","9783319108827"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10882-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}