{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:21Z","timestamp":1725460041160},"publisher-location":"Boston, MA","reference-count":21,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9781402081408"},{"type":"electronic","value":"9781402081415"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/1-4020-8141-3_32","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T10:15:11Z","timestamp":1140516911000},"page":"409-422","source":"Crossref","is-referenced-by-count":0,"title":["Tailoring Recursion to Characterize Non-Deterministic Complexity Classes Over Arbitrary Structures"],"prefix":"10.1007","author":[{"given":"O.","family":"Bournez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Cucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"de Jacobe Naurois","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. -Y.","family":"Marion","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"32_CR1","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.2307\/2586700","volume":"65","author":"A. Blass","year":"2000","unstructured":"A. Blass and Y. Gurevich. The logic of choice. Journal of Symbolic Logic, 65(3): 1264\u20131310, Sept. 2000.","journal-title":"Journal of Symbolic Logic"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"S. Bellantoni. Predicative recursion and the polytime hiearchy. In Peter Clote and Jeffrey B. Remmel, editors, Feasible Mathematics II, Perspectives in Computer Science. Birkhauser, 1994.","DOI":"10.1007\/978-1-4612-2566-9_2"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"S. Bellantoni and S. Cook. A new recursion-theoretic characterization of the poly-time functions. Computational Complexity, 2:97\u2013110, 1992.","journal-title":"Computational Complexity"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"O. Bournez, F. Cucker, P. Jacobe de Naurois, and J.-Y. Marion. Computability over an arbitrary structure. sequential and parallel polynomial time. In Andrew D. Gordon, editor, Foundations of Software Science and Computational Structures, 6th International Conference (FOSSACS\u2019 2003), volume 2620 of Lecture Notes in Computer Science, pages 185\u2013199. Springer, 2003.","DOI":"10.1007\/3-540-36576-1_12"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"P. Clote. Computational models and function algebras. In D. Leivant, editor, LCC\u201994, volume 960 of Lecture Notes in Computer Science, pages 98\u2013130. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60178-3_81"},{"key":"32_CR7","unstructured":"A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pages 24\u201330. North-Holland, Amsterdam, 1962."},{"key":"32_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-1-4612-2822-6_3","volume-title":"Logic from Computer Science","author":"S. Cook","year":"1992","unstructured":"S. Cook. Computability and complexity of higher-type functions. In Y. Moschovakis, editor, Logic from Computer Science, pages 51\u201372. Springer-Verlag, New York, 1992."},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1093\/comjnl\/36.5.400","volume":"36","author":"F. Cucker","year":"1993","unstructured":"F. Cucker. On the complexity of quantifier elimination: the structural approach. The Computer Journal, 36:400\u2013408, 1993.","journal-title":"The Computer Journal"},{"key":"32_CR10","volume-title":"Perspectives in Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1995."},{"key":"32_CR11","unstructured":"R. Fagin. Generalized first order spectra and polynomial time recognizable sets. In R. Karp, editor, Complexity of Computation, pages 43\u201373. SIAM-AMS, 1974."},{"issue":"3","key":"32_CR12","doi-asserted-by":"crossref","first-page":"952","DOI":"10.2307\/2275767","volume":"60","author":"E. Gradel","year":"1995","unstructured":"E. Gradel and Y. Gurevich. Tailoring recursion for complexity. Journal of Symbolic Logic, 60(3):952\u2013969, Sept. 1995.","journal-title":"Journal of Symbolic Logic"},{"issue":"1","key":"32_CR13","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E. Gradel","year":"1998","unstructured":"Erich Gradel and Yuri Gurevich. Metafinite model theory. Information and Computation, 140(1):26\u201381, 10 January 1998.","journal-title":"Information and Computation"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Erich Gradel and Klaus Meer. Descriptive complexity theory over the real numbers. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 315\u2013324, Las Vegas, Nevada, 29 May\u20131 June 1995.","DOI":"10.1145\/225058.225151"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Algebras of feasible functions. In Twenty Fourth Symposium on Foundations of Computer Science, pages 210\u2013214. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.5"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"D. Leivant. Predicative recurrence and computational complexity I: Word recurrence and poly-time. In Peter Clote and Jeffery Remmel, editors, Feasible Mathematics II, pages 320\u2013343. Birkhauser, 1994.","DOI":"10.1007\/978-1-4612-2566-9_11"},{"issue":"12","key":"32_CR18","doi-asserted-by":"crossref","first-page":"167","DOI":"10.3233\/FI-1993-191-207","volume":"19","author":"D. Leivant","year":"1993","unstructured":"D. Leivant and J-Y Marion. Lambda calculus characterizations of poly-time. Fundamenta Informaticae, 19(1,2):167,184, September 1993.","journal-title":"Fundamenta Informaticae"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"D. Leivant and J.-Y. Marion. Ramified recurrence and computational complexity II: substitution and poly-space. In L. Pacholski and J. Tiuryn, editors, Computer Science Logic, 8th Workshop, CSL\u201994, volume 933 of Lecture Notes in Computer Science, pages 369\u2013380, Kazimierz, Poland, 1995. Springer-Verlag.","DOI":"10.1007\/BFb0022277"},{"key":"32_CR20","unstructured":"B. Poizat. Les Petits Cailloux. Aleas, 1995."},{"key":"32_CR21","first-page":"319","volume":"7","author":"V. Sazonov","year":"1980","unstructured":"V. Sazonov. Polynomial computability and recursivity in finite domains. Elektronische Informationsverarbeitung und Kybernetik, 7:319\u2013323, 1980.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T01:11:26Z","timestamp":1627089086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9781402081408","9781402081415"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_32","relation":{},"ISSN":["1571-5736"],"issn-type":[{"type":"print","value":"1571-5736"}],"subject":[],"published":{"date-parts":[[2004]]}}}