{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:05:50Z","timestamp":1743105950154,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031643088"},{"type":"electronic","value":"9783031643095"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-64309-5_20","type":"book-chapter","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T22:01:49Z","timestamp":1719871309000},"page":"252-264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recursion-Theoretic Alternation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5729-1078","authenticated-orcid":false,"given":"Eduardo","family":"Skapinakis","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M.: Quasipolynomial size circuit classes. In: 1992 Seventh Annual Structure in Complexity Theory Conference, pp. 86\u201387. IEEE Computer Society (1992)","DOI":"10.1109\/SCT.1992.215383"},{"issue":"3","key":"20_CR2","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"DAM Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC$${}^1$$. J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the polytime functions. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 283\u2013293 (1992)","DOI":"10.1145\/129712.129740"},{"issue":"1\u20132","key":"20_CR4","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. Theor. Comput. Sci. 318(1\u20132), 57\u201378 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"2280","DOI":"10.1007\/BF01629435","volume":"20","author":"AP Bel\u2019tyukov","year":"1982","unstructured":"Bel\u2019tyukov, A.P.: A machine description and the hierarchy of initial Grzegorczyk classes. J. Sov. Math. 20, 2280\u20132289 (1982)","journal-title":"J. Sov. Math."},{"key":"20_CR6","unstructured":"Bloch, S.: Alternating function classes within P. Technical report, University of Manitoba Computer Science Department (1992)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Bloch, S.: Functional characterizations of uniform log-depth and polylog-depth circuit families. In: Computational Complexity Conference, pp. 193\u2013206. Citeseer (1992)","DOI":"10.1109\/SCT.1992.215394"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0020-0190(92)90180-4","volume":"41","author":"SR Buss","year":"1992","unstructured":"Buss, S.R.: The graph of multiplication is equivalent to counting. Inf. Process. Lett. 41(4), 199\u2013201 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Clote, P.: Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, $$AC^k$$, $$NC^k$$ and NC, pp. 49\u201369. Birkh\u00e4user Boston, Boston, MA (1990)","DOI":"10.1007\/978-1-4612-3466-1_4"},{"issue":"1\u20132","key":"20_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0304-3975(96)00051-5","volume":"178","author":"P Clote","year":"1997","unstructured":"Clote, P.: Nondeterministic stack register machines. Theor. Comput. Sci. 178(1\u20132), 37\u201376 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Clote, P.: Computation models and function algebras. In: Studies in Logic and the Foundations of Mathematics, vol.\u00a0140, pp. 589\u2013681. Elsevier (1999)","DOI":"10.1016\/S0049-237X(99)80033-0"},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-030-39951-1_6","volume-title":"Foundations of Information and Knowledge Systems","author":"F Ferrarotti","year":"2020","unstructured":"Ferrarotti, F., Gonz\u00e1lez, S., Schewe, K.-D., Turull-Torres, J.M.: Proper hierarchies in polylogarithmic time and absence of complete problems. In: Herzig, A., Kontinen, J. (eds.) FoIKS 2020. LNCS, vol. 12012, pp. 90\u2013105. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-39951-1_6"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Ferrarotti, F., Gonz\u00e1lez, S., Schewe, K.D., Turull-Torres, J.M.: The polylog-time hierarchy captured by restricted second-order logic. In: 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 133\u2013140. IEEE (2018)","DOI":"10.1109\/SYNASC.2018.00032"},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2021.02.003","volume":"119","author":"F Ferrarotti","year":"2021","unstructured":"Ferrarotti, F., Gonz\u00e1lez, S., Torres, J.M.T., Van den Bussche, J., Virtema, J.: Descriptive complexity of deterministic polylogarithmic time and space. J. Comput. Syst. Sci. 119, 145\u2013163 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Leivant, D.: A foundational delineation of computational feasibility. In: Proceedings 1991 Sixth Annual IEEE Symposium on Logic in Computer Science, pp. 2\u201311. IEEE Computer Society (1991)","DOI":"10.1109\/LICS.1991.151625"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Leivant, D.: A characterization of NC by tree recurrence. In: Proceedings 39th Annual Symposium on Foundations of Computer Science, pp. 716\u2013724. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743522"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/malq.200610056","volume":"54","author":"I Oitavem","year":"2008","unstructured":"Oitavem, I.: Characterizing PSPACE with pointers. Math. Log. Q. 54(3), 323\u2013329 (2008)","journal-title":"Math. Log. Q."},{"issue":"8","key":"20_CR19","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. Log. 162(8), 661\u2013666 (2011)","journal-title":"Ann. Pure Appl. Log."},{"key":"20_CR20","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. Theor. Comput. Sci. 900, 25\u201334 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Paul, W.J., Pippenger, N., Szemeredi, E., Trotter, W.T.: On determinism versus non-determinism and related problems. In: 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), pp. 429\u2013438 (1983)","DOI":"10.1109\/SFCS.1983.39"},{"issue":"1","key":"20_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0304-3975(96)00288-5","volume":"188","author":"KW Regan","year":"1997","unstructured":"Regan, K.W., Vollmer, H.: Gap-languages and log-time complexity classes. Theor. Comput. Sci. 188(1), 101\u2013116 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"20_CR23","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. Log. 27(2), 177\u2013188 (1988)","journal-title":"Arch. Math. Log."},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Borel sets and circuit complexity. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 61\u201369 (1983)","DOI":"10.1145\/800061.808733"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Smullyan, R.M.: Theory of Formal Systems. Princeton University Press, Princeton (1961)","DOI":"10.1515\/9781400882007"},{"issue":"2","key":"20_CR26","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0207018","volume":"7","author":"C Wrathall","year":"1978","unstructured":"Wrathall, C.: Rudimentary predicates and relative computation. SIAM J. Comput. 7(2), 194\u2013209 (1978)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Twenty Years of Theoretical and Practical Synergies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-64309-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T06:44:07Z","timestamp":1732344247000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-64309-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031643088","9783031643095"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-64309-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"2 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}