{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T21:43:05Z","timestamp":1665524585712},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"7-8","license":[{"start":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T00:00:00Z","timestamp":1651536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T00:00:00Z","timestamp":1651536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Udo Keller Stiftung"},{"name":"Centro de Matem\u00e1tica e Aplica\u00e7\u00f5es, Universidade Nova de Lisboa"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00153-022-00828-4","type":"journal-article","created":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T19:18:13Z","timestamp":1651605493000},"page":"1129-1144","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Implicit recursion-theoretic characterizations of counting classes"],"prefix":"10.1007","volume":"61","author":[{"given":"Ugo","family":"Dal Lago","sequence":"first","affiliation":[]},{"given":"Reinhard","family":"Kahle","sequence":"additional","affiliation":[]},{"given":"Isabel","family":"Oitavem","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,3]]},"reference":[{"key":"828_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 poly-time functions. Comput. Complex. 2, 97\u2013110 (1992)","journal-title":"Comput. Complex."},{"key":"828_CR2","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2003.10.021","volume":"318","author":"S Bellantoni","year":"2004","unstructured":"Bellantoni, S., Oitavem, I.: Separating NC along the $$\\delta $$ axis. Theoret. Comput. Sci. 318, 57\u201378 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"828_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1093\/logcom\/exq002","volume":"22","author":"AM Ben-Amram","year":"2012","unstructured":"Ben-Amram, A.M., Loff, B., Oitavem, I.: Monotonicity constraints in characterizations of PSPACE. J. Log. Comput. 22, 179\u2013195 (2012)","journal-title":"J. Log. Comput."},{"issue":"2","key":"828_CR4","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s001530100105","volume":"41","author":"A Cantini","year":"2002","unstructured":"Cantini, A.: Polytime, combinatory logic and positive safe induction. Arch. Math. Logic 41(2), 169\u2013189 (2002)","journal-title":"Arch. Math. Logic"},{"key":"828_CR5","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Logic, Methodology, and Philsophy of Science II, pp. 24\u201330. North-Holland (1965)"},{"key":"828_CR6","unstructured":"Dal Lago, U., Kahle, R., Oitavem, I.: A recursion-theoretic characterization of the probabilistic class PP. In: Bonchi, F., Puglisi, S.J. (eds.) Mathematical Foundations of Computer Science 2021. Leibniz International Proceedings in Informatics (LIPIcs), vol. 202, pp. 35:1\u201335:12. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021)"},{"key":"828_CR7","doi-asserted-by":"crossref","unstructured":"Ferreira, F.: Polynomial time computable arithmetic. In: Sieg, W. (ed.) Logic and Computation, Contemporary Mathematics, vol. 106, pp. 137\u2013156. American Mathematical Society (1990)","DOI":"10.1090\/conm\/106\/1057819"},{"key":"828_CR8","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1006\/jcss.1995.1036","volume":"50","author":"F Green","year":"1995","unstructured":"Green, F., K\u00f6bler, J., Regan, K.W., Schwentick, T., Tor\u00e1n, J.: The power of the middle bit of a $$\\#$$P function. J. Comput. Syst. Sci. 50, 456\u2013467 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"828_CR9","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1016\/j.apal.2012.05.006","volume":"164","author":"R Kahle","year":"2013","unstructured":"Kahle, R., Oitavem, I.: Applicative theories for the polynomial hierarchy of time and its levels. Ann. Pure Appl. Logic 164(6), 663\u2013675 (2013)","journal-title":"Ann. Pure Appl. Logic"},{"key":"828_CR10","doi-asserted-by":"crossref","unstructured":"Leivant, D.: Ramified recurrence and computational complexity I: Word recurrence and poly-time. In: Remmel, J.B., Clote, P. (eds.) Feasible Mathematics II, pp. 320\u2013343. Birkh\u00e4user (1995)","DOI":"10.1007\/978-1-4612-2566-9_11"},{"issue":"1","key":"828_CR11","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1002\/malq.200310070","volume":"50","author":"I Oitavem","year":"2004","unstructured":"Oitavem, I.: Characterizing NC with tier 0 pointers. Math. Log. Q. 50(1), 9\u201317 (2004)","journal-title":"Math. Log. Q."},{"issue":"3","key":"828_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1002\/malq.200610056","volume":"54","author":"I Oitavem","year":"2008","unstructured":"Oitavem, I.: Characterizing PSPACE with pointers. Math. Log. Q. 54(3), 317\u2013323 (2008)","journal-title":"Math. Log. Q."},{"issue":"8","key":"828_CR13","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1016\/j.apal.2011.01.010","volume":"162","author":"I Oitavem","year":"2011","unstructured":"Oitavem, I.: A recursion-theoretic approach to NP. Ann. Pure Appl. Logic 162(8), 661\u2013666 (2011)","journal-title":"Ann. Pure Appl. Logic"},{"key":"828_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2021.11.016","volume":"900","author":"I Oitavem","year":"2022","unstructured":"Oitavem, I.: The polynomial hierarchy of functions and its levels. Theoret. Comput. Sci. 900, 25\u201334 (2022)","journal-title":"Theoret. Comput. Sci."},{"key":"828_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01620765","volume":"27","author":"H Simmons","year":"1988","unstructured":"Simmons, H.: The realm of primitive recursion. Arch. Math. Logic 27, 177\u2013188 (1988)","journal-title":"Arch. Math. Logic"},{"key":"828_CR16","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0890-5401(03)00086-5","volume":"185","author":"T Strahm","year":"2003","unstructured":"Strahm, T.: Theories with self-application and computational complexity. Inf. Comput. 185, 263\u2013297 (2003)","journal-title":"Inf. Comput."},{"key":"828_CR17","doi-asserted-by":"crossref","unstructured":"Strahm, T.: Weak theories of operations and types. In: Schindler, R. (ed) Ways of Proof Theory, Ontos Verlag, pp. 441\u2013468 (2010)","DOI":"10.1515\/9783110324907.441"},{"key":"828_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"key":"828_CR19","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0304-3975(95)00237-5","volume":"163","author":"H Vollmer","year":"1996","unstructured":"Vollmer, H., Wagner, K.W.: Recursion theoretic characterizations of complexity classes of counting functions. Theoret. Comput. Sci. 163, 245\u2013258 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"828_CR20","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(86)90141-6","volume":"47","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W.: Some observations on the connection between counting and recursion. Theoret. Comput. Sci. 47, 131\u2013147 (1986)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00828-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-022-00828-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00828-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T21:04:57Z","timestamp":1665522297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-022-00828-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,3]]},"references-count":20,"journal-issue":{"issue":"7-8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["828"],"URL":"https:\/\/doi.org\/10.1007\/s00153-022-00828-4","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,3]]},"assertion":[{"value":"23 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}