{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T17:39:15Z","timestamp":1648748355411},"reference-count":34,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1051\/ita\/2010020","type":"journal-article","created":{"date-parts":[[2010,10,4]],"date-time":"2010-10-04T12:06:45Z","timestamp":1286194005000},"page":"379-418","source":"Crossref","is-referenced-by-count":0,"title":["Function operators spanning the arithmetical and the polynomial hierarchy"],"prefix":"10.1051","volume":"44","author":[{"given":"Armin","family":"Hemmerling","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2010,10,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"Buss","year":"1991","journal-title":"Inf. Comput."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J.L. Balcazar, J. Diaz and J. Gabarro,Structural complexity I and II. Springer-Verlag, Berlin (1990).","DOI":"10.1007\/978-3-642-75357-2"},{"key":"R3","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S009753979528175X","volume":"29","author":"Bellantoni","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"R4","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"Cai","year":"1988","journal-title":"SIAM Journal on Computing"},{"key":"R5","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"Cai","year":"1989","journal-title":"SIAM Journal on Computing"},{"key":"R6","unstructured":"S.B. Cooper,Computability theory. Chapman & Hall\/CRC, Boca Raton (2004)."},{"key":"R7","unstructured":"D.-Z. Du and K.-I. Ko,Theory of computational complexity. Wiley-Interscience, New York (2000)."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R.L. Epstein, R. Haas and R.L. Kramer,Hierarchies of sets and degrees below0'. In: Logic Year (1979\/80), Univ. of Connecticut, edited by M. Lerman, J.H. Schmerl, R.I. Soare. LN in Math 859. Springer Verlag, 32\u201348.","DOI":"10.1007\/BFb0090937"},{"key":"R9","unstructured":"Y.L. Ershov, A hierarchy of sets. I; II; III. Algebra i Logica7(1968) no. 1, 47\u201374; no. 4, 15\u201347;9(1970), no. 1, 34\u201351 (English translation by Plenum P.C.)."},{"key":"R10","unstructured":"M.R. Garey and D.S. Johnson,Computers and intractability \u2013 a guide to the theory of NP\u2013completeness. W.H. Freeman, San Francisco (1979)."},{"key":"#cr-split#-R11.1","unstructured":"F. Hausdorff, W. de Gruyter & Co., Berlin and Leipzig (1914);"},{"key":"#cr-split#-R11.2","unstructured":"Reprint: Chelsea P.C., New York (1949)."},{"key":"R12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/s00153-005-0317-8","volume":"45","author":"Hemmerling","year":"2006","journal-title":"Arch. Math. Logic"},{"key":"R13","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.entcs.2004.06.034","volume":"120","author":"Hemmerling","year":"2005","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Krajicek,Bounded arithmetic, propositional logic, and complexity theory. Cambridge Univ. Press (1995).","DOI":"10.1017\/CBO9780511529948"},{"key":"R15","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"Krentel","year":"1988","journal-title":"J. Comput. Syst. Sci."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A.I. Malcev,Algorithmen und rekursive Funktionen. Akademie-Verlag, Berlin (1974).","DOI":"10.1007\/978-3-322-85356-1"},{"key":"R17","unstructured":"P. Odifreddi,Classical recursion theory. North-Holland P.C., Amsterdam (1989)."},{"key":"R18","unstructured":"C.H. Papadimitriou,Computational complexity. Addison Wesley P.C., Reading (1994)."},{"key":"R19","unstructured":"C. Parsons, Hierarchies of primitive recursive functions. Zeitschr. f. Math. Logik u. Grundl. d. Math.14(1968) 357\u2013376."},{"key":"R20","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1090\/S0002-9939-1950-0038912-1","volume":"72","author":"Robinson","year":"1950","journal-title":"Proc. Am. Math. Soc."},{"key":"R21","unstructured":"H. Rogers Jr,Theory of recursive functions and effective computability. McGraw-Hill, New York (1967)."},{"key":"R22","unstructured":"H.E. Rose,Subrecursion: functions and hierarchies. Clarendon Press, Oxford (1984)."},{"key":"R23","unstructured":"J. Rothe,Complexity theory and cryptology. Springer-Verlag, Berlin (2005)."},{"key":"R24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BF01982053","volume":"12","author":"Schwichtenberg","year":"1969","journal-title":"Arch. Math. Logic"},{"key":"R25","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01374525","volume":"25","author":"Selman","year":"1992","journal-title":"Math. Syst. Theory"},{"key":"R26","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"Selman","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"R27","doi-asserted-by":"crossref","first-page":"644","DOI":"10.2307\/1970028","volume":"69","author":"Shoenfield","year":"1959","journal-title":"Ann. Math."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"R.I. Soare,Recursively enumerable sets and degrees. Springer-Verlag, Berlin (1987).","DOI":"10.1007\/978-3-662-02460-7"},{"key":"R29","doi-asserted-by":"crossref","first-page":"284","DOI":"10.2307\/420992","volume":"2","author":"Soare","year":"1996","journal-title":"Bulletin of symbolic Logic"},{"key":"R30","unstructured":"R.I. Soare,Computability theory and applications. Springer-Verlag, Berlin, forthcoming."},{"key":"R31","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"Wagner","year":"1990","journal-title":"SIAM Journal on Computing"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"G. Wechsung,Vorlesungen zur Komplexit\u00e4tstheorie. B.G. Teubner, Stuttgart (2000).","DOI":"10.1007\/978-3-322-80024-4"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"K. Weihrauch,Computability. Springer-Verlag, Berlin (1987).","DOI":"10.1007\/978-3-642-69965-8"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2010020\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T06:00:27Z","timestamp":1559714427000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2010020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":34,"journal-issue":{"issue":"3"},"alternative-id":["ita09030"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2010020","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7]]}}}