{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:01Z","timestamp":1760202541771},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540008972"},{"type":"electronic","value":"9783540365761"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36576-1_12","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:42:17Z","timestamp":1181616137000},"page":"185-199","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Bournez","sequence":"first","affiliation":[]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[]},{"given":"Paulin Jacob\u00e9","family":"de Naurois","sequence":"additional","affiliation":[]},{"given":"Jean-Yves","family":"Marion","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,28]]},"reference":[{"key":"12_CR1","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":"12_CR2","doi-asserted-by":"crossref","unstructured":"Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation. Springer Verlag, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Olivier Bournez, Jean-Yves Marion, and Paulin de Naurois. Safe recursion over an arbitrary structure: Deterministic polynomial time. Technical report, LORIA, 2002.","DOI":"10.1016\/S1571-0661(03)00005-7"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions, and universal machines. Bulletin of the American Mathematical Society, 21:1\u201346, 1989.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"P. Clote. Computational models and function algebras. In D. Leivant, editor, LCC\u201994, volume 960, pages 98\u2013130, 1995.","DOI":"10.1007\/3-540-60178-3_81"},{"key":"12_CR6","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":"12_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-1-4612-2822-6_3","volume-title":"Logic from Computer Science","author":"S. A. Cook","year":"1992","unstructured":"S. A. Cook. Computability and complexity of higher-type functions. In Y. Moschovakis, editor, Logic from Computer Science, pages 51\u201372. Springer-Verlag, New York, 1992."},{"issue":"1","key":"12_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(94)00069-7","volume":"133","author":"F. Cucker","year":"1994","unstructured":"F. Cucker, M. Shub, and S. Smale. Separation of complexity classes in Koiran\u2019s weak model. Theoretical Computer Science, 133(1):3\u201314, 11 October1994.","journal-title":"Theoretical Computer Science"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/0885-064X(92)90024-6","volume":"8","author":"F. Cucker","year":"1992","unstructured":"F. Cucker. P\u211d\u2260 NC\u211d. Journal of Complexity, 8:230\u2013238, 1992.","journal-title":"Journal of Complexity"},{"key":"12_CR10","volume-title":"Perspectives in Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1995."},{"key":"12_CR11","unstructured":"R. Fagin. Generalized first order spectra and polynomial time recognizable sets. In R. Karp, editor, Complexity of Computation, pages 43\u201373. SIAMAMS, 1974."},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"92","DOI":"10.2307\/2275252","volume":"59","author":"J. B. Goode","year":"1994","unstructured":"J. B. Goode. Accessible telephone directories. The Journal of Symbolic Logic, 59(1):92\u2013105, March 1994.","journal-title":"The Journal of Symbolic Logic"},{"key":"12_CR13","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":"12_CR14","unstructured":"M. Hofmann. Type systems for polynomial-time computation, 1999. Habilitation."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"N. Jones. The expressive power of higher order types or, life without cons. 2000.","DOI":"10.1017\/S0956796800003889"},{"key":"12_CR17","first-page":"177","volume-title":"Lecture Notes in Computer Science","author":"Daniel Leivant","year":"1995","unstructured":"D. Leivant. Intrinsic theories and computational complexity. In LCC\u201994, number 960, pages 177\u2013194, 1995."},{"issue":"12","key":"12_CR18","first-page":"167,184","volume":"19","author":"D. Leivant","year":"1993","unstructured":"D. Leivant and J-Y Marion. Lambda calculus characterizations of polytime. fi, 19(1,2):167,184, September 1993.","journal-title":"Lambda calculus characterizations of polytime"},{"key":"12_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/3-540-60178-3","volume-title":"Ramified recurrence and computational complexity II: substitution and poly-space","author":"D. Leivant","year":"1995","unstructured":"Daniel Leivant and Jean-Yves 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."},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0885-064X(92)90007-X","volume":"8","author":"K. Meer","year":"1992","unstructured":"K. Meer. A note on a P \u2260NP result for a restricted class of real machines. Journal of Complexity, 8:451\u2013453, 1992.","journal-title":"Journal of Complexity"},{"key":"12_CR21","first-page":"435","volume-title":"Une remarque `a propos des machines sur _ introduites par Blum, Shub et Smale","author":"C. Michaux","year":"1989","unstructured":"Christian Michaux. Une remarque `a propos des machines sur _ introduites par Blum, Shub et Smale. In C. R. Acad. Sc. de Paris, volume 309 of 1, pages 435\u2013437. 1989."},{"key":"12_CR22","unstructured":"J-Y Marion and J-Y Moyen. Efficient first order functional program interpreter with time bound certifications. In LPAR, volume 1955, pages 25\u201342. Springer, Nov 2000."},{"key":"12_CR23","unstructured":"Bruno Poizat. Les petits cailloux. al\u00e9as, 1995."},{"key":"12_CR24","first-page":"117","volume":"11","author":"B. Kapron","year":"2001","unstructured":"B. Kapron R. Irwin and J. Royer. On characterizations of the basic feasible functionals. 11:117\u2013153, 2001.","journal-title":"On characterizations of the basic feasible functionals"},{"key":"12_CR25","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":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36576-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T10:41:19Z","timestamp":1683888079000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36576-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540008972","9783540365761"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-36576-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]},"assertion":[{"value":"28 February 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}