{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:55Z","timestamp":1740109375977,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100011958","name":"danmarks frie forskningsfond","doi-asserted-by":"publisher","award":["115554"],"award-info":[{"award-number":["115554"]}],"id":[{"id":"10.13039\/501100011958","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00224-022-10074-z","type":"journal-article","created":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T21:02:31Z","timestamp":1656536551000},"page":"437-472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Subclasses of Ptime Interpreted by Programming Languages"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4157-8768","authenticated-orcid":false,"given":"Siddharth","family":"Bhaskar","sequence":"first","affiliation":[]},{"given":"Cynthia","family":"Kop","sequence":"additional","affiliation":[]},{"given":"Jakob Grue","family":"Simonsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,29]]},"reference":[{"issue":"4","key":"10074_CR1","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1145\/76359.76370","volume":"36","author":"EW Allender","year":"1989","unstructured":"Allender, E.W.: P-uniform circuit complexity. J. ACM 36(4), 912\u2013928 (1989)","journal-title":"J. ACM"},{"key":"10074_CR2","doi-asserted-by":"crossref","unstructured":"Alton, D.A.: \u201cNatural\u201d Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach, pp. 248\u2013285. London Mathematical Society Lecture Note Series. Cambridge University Press (1980)","DOI":"10.1017\/CBO9780511629181.011"},{"key":"10074_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"issue":"2","key":"10074_CR4","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"Blum, M.: A machine-independent theory of the complexity of recursive functions. J. ACM 14(2), 322\u2013336 (1967)","journal-title":"J. ACM"},{"key":"10074_CR5","doi-asserted-by":"crossref","unstructured":"Bonfante, G., Kahle, R., Marion, J.Y., Oitavem, I.: Towards an implicit characterization of NCk. In: \u00c9sik, Z. (ed.) Computer Science Logic, pp 212\u2013224. Springer, Berlin (2006)","DOI":"10.1007\/11874683_14"},{"issue":"1","key":"10074_CR6","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"},{"issue":"1","key":"10074_CR7","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/S0022-0000(73)80048-0","volume":"7","author":"OH Ibarra","year":"1973","unstructured":"Ibarra, O.H.: On two-way multihead automata. J. Comput. Syst. Sci. 7(1), 28\u201336 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"10074_CR8","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2003.001.0001","volume-title":"Computability and Complexity. From a Programming Perspective","author":"ND Jones","year":"1997","unstructured":"Jones, N.D.: Computability and Complexity. From a Programming Perspective. MIT Press, London (1997)"},{"issue":"1","key":"10074_CR9","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0304-3975(98)00357-0","volume":"228","author":"ND Jones","year":"1999","unstructured":"Jones, N.D.: LOGSPACE and PTIME characterized by programming languages. Theor. Comput. Sci. 228(1), 151\u2013174 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10074_CR10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1017\/S0956796800003889","volume":"11","author":"ND Jones","year":"2001","unstructured":"Jones, N.D.: The expressive power of higher-order types or, life without CONS. J. Funct. Program. 11(1), 55\u201394 (2001)","journal-title":"J. Funct. Program."},{"key":"10074_CR11","doi-asserted-by":"crossref","unstructured":"Kop, C., Simonsen, J.G.: The power of non-determinism in higher-order implicit complexity: characterising complexity classes using non-deterministic cons-free programming. In: Yang, H. (ed.) Programming Languages and Systems, Lecture notes in computer science, pp 668\u2013695. Springer, Berlin (2017)","DOI":"10.1007\/978-3-662-54434-1_25"},{"key":"10074_CR12","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y.N.: Abstract Recursion and Intrinsic Complexity. Lecture Notes in Logic. Cambridge University Press (2018)","DOI":"10.1017\/9781108234238"},{"issue":"1","key":"10074_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jlap.2009.02.005","volume":"79","author":"K-H Niggl","year":"2010","unstructured":"Niggl, K.-H., Wunderlich, H.: Implicit characterizations of FPTIME and NC revisited. J. Logic Algebraic Program 79(1), 47\u201360 (2010). Special Issue: Logic, Computability and Topology in Computer Science: A New Perspective for Old Disciplines","journal-title":"J. Logic Algebraic Program"},{"key":"10074_CR14","unstructured":"Rabin, M.O.: Degree of difficulty of computing a function and a partial ordering of recursive sets. Technical Report 2, Hebrew University (1960)"},{"issue":"2","key":"10074_CR15","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"WL Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 21(2), 218\u2013235 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10074_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22(3), 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"10074_CR17","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Thomson Course Technology (2006)"},{"key":"10074_CR18","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H.: Time and tape bounded auxiliary pushdown automata. In: Gruska, J. (ed.) Mathematical Foundations of Computer Science 1977, pp 493\u2013503. Springer, Berlin (1977)","DOI":"10.1007\/3-540-08353-7_172"},{"key":"10074_CR19","unstructured":"Tserunyan, A.: (1) Finite generators for countable group actions; (2) Finite index pairs of equivalence relations; (3) Complexity measures for recursive programs. PhD thesis, University of California, Los Angeles (2013)"},{"issue":"2","key":"10074_CR20","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H Venkateswaran","year":"1991","unstructured":"Venkateswaran, H.: Properties that characterize logcfl. J. Comput. Syst. Sci. 43(2), 380\u2013404 (1991)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10074-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10074-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10074-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T01:02:12Z","timestamp":1688605332000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10074-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10074"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10074-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,6,29]]},"assertion":[{"value":"10 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}