{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T14:48:30Z","timestamp":1763563710159,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_12","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"136-147","source":"Crossref","is-referenced-by-count":2,"title":["A Characterization of NC k by First Order Functional Programs"],"prefix":"10.1007","author":[{"given":"Jean-Yves","family":"Marion","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romain","family":"P\u00e9choux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Amadio, R.: Synthesis of max-plus quasi-interpretations. Fundamenta Informaticae\u00a065(1\u20132) (2005)","DOI":"10.3233\/FUN-2005-65303"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-540-24727-2_4","volume-title":"Foundations of Software Science and Computation Structures","author":"P. Baillot","year":"2004","unstructured":"Baillot, P., Mogbil, V.: Soft lambda-calculus: A language for polynomial time computation. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol.\u00a02987, pp. 27\u201341. Springer, Heidelberg (2004)"},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. Barrington","year":"1990","unstructured":"Barrington, D., Immerman, N., Straubing, H.: On uniformity within NC. J. of Computer System Science\u00a041(3), 274\u2013306 (1990)","journal-title":"J. of Computer System Science"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the poly-time functions. Computational Complexity\u00a02, 97\u2013110 (1992)","journal-title":"Computational Complexity"},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01202288","volume":"4","author":"S. Bloch","year":"1994","unstructured":"Bloch, S.: Function-algebraic characterizations of log and polylog parallel time. Computational complexity\u00a04(2), 175\u2013205 (1994)","journal-title":"Computational complexity"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","first-page":"212","volume-title":"Computer Science Logic","author":"R. Kahle","year":"2006","unstructured":"Kahle, R., Marion, J.-Y., Bonfante, G., Oitavem, I.: Towards an implicit characterization of NC k . In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 212\u2013224. Springer, Heidelberg (2006)"},{"key":"12_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45575-2_46","volume-title":"Perspectives of System Informatics","author":"G. Bonfante","year":"2001","unstructured":"Bonfante, G., Marion, J.-Y., Moyen, J.-Y.: On lexicographic termination ordering with space bound certifications. In: Bj\u00f8rner, D., Broy, M., Zamulin, A.V. (eds.) PSI 2001. LNCS, vol.\u00a02244, Springer, Heidelberg (2001)"},{"key":"12_CR8","unstructured":"Bonfante, G., Marion, J.-Y., Moyen, J.-Y., P\u00e9choux, R.: Synthesis of quasi-interpretations. In: LCC2005, LICS affiliated Workshop (2005), http:\/\/hal.inria.fr"},{"key":"12_CR9","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/11916277_7","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"G. Bonfante","year":"2006","unstructured":"Bonfante, G., Marion, J.-Y., P\u00e9choux, R.: A characterization of alternating log time by first order functional programs. In: Hermann, M., Voronkov, A. (eds.) LPAR 2006. LNCS (LNAI), vol.\u00a04246, pp. 90\u2013104. Springer, Heidelberg (2006)"},{"key":"12_CR10","unstructured":"Bonfante, G., Marion, J.Y., Moyen, J.Y.: Quasi-interpretations, a way to control resources. TCS (2007)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Buss, S.: The boolean formula value problem is in ALOGTIME. In: STOC, pp. 123\u2013131 (1987)","DOI":"10.1145\/28395.28409"},{"key":"12_CR12","first-page":"49","volume-title":"Workshop on Feasible Math","author":"P. Clote","year":"1989","unstructured":"Clote, P.: Sequential, machine-independent characterizations of the parallel complexity classes ALOGTIME, AC k , NC k and NC. In: Buss, R., Scott, P. (eds.) Workshop on Feasible Math, pp. 49\u201369. Birkh\u00e4user, Basel (1989)"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/3-540-60178-3_81","volume-title":"Logic and Computational Complexity","author":"P. Clote","year":"1995","unstructured":"Clote, P.: Computational models and function algebras. In: Leivant, D. (ed.) LCC 1994. LNCS, vol.\u00a0960, pp. 98\u2013130. Springer, Heidelberg (1995)"},{"key":"12_CR14","first-page":"24","volume-title":"Conf. on Logic, Methodology, and Philosophy of Science","author":"A. Cobham","year":"1962","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Conf. on Logic, Methodology, and Philosophy of Science, pp. 24\u201330. North-Holland, Amsterdam (1962)"},{"issue":"1\/2","key":"12_CR15","first-page":"240","volume":"87","author":"K.J. Compton","year":"1990","unstructured":"Compton, K.J., Laflamme, C.: An algebra and a logic for NC. Inf. Comput.\u00a087(1\/2), 240\u2013262 (1990)","journal-title":"Inf. Comput."},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-74915-8_21","volume-title":"Computer Science Logic","author":"M. Gaboardi","year":"2007","unstructured":"Gaboardi, M., Rocca, S.R.D.: A soft type assignment system for \u03bb-calculus. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 253\u2013267. Springer, Heidelberg (2007)"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1006\/inco.1998.2700","volume":"143","author":"J.-Y. Girard","year":"1998","unstructured":"Girard, J.-Y.: Light linear logic. Inf. and Comp.\u00a0143(2), 175\u2013204 (1998)","journal-title":"Inf. and Comp."},{"issue":"1","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(92)90386-T","volume":"97","author":"J.Y. Girard","year":"1992","unstructured":"Girard, J.Y., Scedrov, A., Scott, P.: Bounded linear logic. Theoretical Computer Science\u00a097(1), 1\u201366 (1992)","journal-title":"Theoretical Computer Science"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Hofmann, M.: Programming languages capturing complexity classes. SIGACT News Logic Column 9 (2000)","DOI":"10.1145\/346048.346051"},{"issue":"4","key":"12_CR20","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1145\/322217.322230","volume":"27","author":"G. Huet","year":"1980","unstructured":"Huet, G.: Confluent reductions: Abstract properties and applications to term rewriting systems. Journal of the ACM\u00a027(4), 797\u2013821 (1980)","journal-title":"Journal of the ACM"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/11494645_33","volume-title":"New Computational Paradigms","author":"L. Kristiansen","year":"2005","unstructured":"Kristiansen, L., Jones, N.D.: The flow of data and the complexity of algorithms. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol.\u00a03526, pp. 263\u2013274. Springer, Heidelberg (2005)"},{"issue":"1-2","key":"12_CR22","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.tcs.2003.10.018","volume":"318","author":"Y. Lafont","year":"2004","unstructured":"Lafont, Y.: Soft linear logic and polynomial time. Theoretical Computer Science\u00a0318(1-2), 163\u2013180 (2004)","journal-title":"Theoretical Computer Science"},{"key":"12_CR23","first-page":"320","volume-title":"Feasible Mathematics II","author":"D. Leivant","year":"1994","unstructured":"Leivant, D.: Predicative recurrence and computational complexity I: Word recurrence and poly-time. In: Feasible Mathematics II, pp. 320\u2013343. Birkh\u00e4user, Basel (1994)"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Leivant, D.: A characterization of NC by tree recurrence. In: FOCS 1998, pp. 716\u2013724 (1998)","DOI":"10.1109\/SFCS.1998.743522"},{"issue":"1-2","key":"12_CR25","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0304-3975(99)00209-1","volume":"236","author":"D. Leivant","year":"2000","unstructured":"Leivant, D., Marion, J.-Y.: A characterization of alternating log time by ramified recurrence. TCS\u00a0236(1-2), 192\u2013208 (2000)","journal-title":"TCS"},{"key":"12_CR26","series-title":"Lecture Notes in Artificial Intelligence","first-page":"25","volume-title":"Logic for Programming and Automated Reasoning","author":"J.-Y. Marion","year":"2000","unstructured":"Marion, J.-Y., Moyen, J.-Y.: Efficient first order functional program interpreter with time bound certifications. In: Parigot, M., Voronkov, A. (eds.) LPAR 2000. LNCS (LNAI), vol.\u00a01955, pp. 25\u201342. Springer, Heidelberg (2000)"},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11737414_12","volume-title":"Functional and Logic Programming","author":"J.-Y. Marion","year":"2006","unstructured":"Marion, J.-Y., P\u00e9choux, R.: Resource analysis by sup-interpretation. In: Hagiya, M., Wadler, P. (eds.) FLOPS 2006. LNCS, vol.\u00a03945, pp. 163\u2013176. Springer, Heidelberg (2006)"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Niggl, K.-H., Wunderlich, H.: Certifying polynomial time and linear\/polynomial space for imperative programs. SIAM J. on Computing (to appear)","DOI":"10.1137\/S0097539704445597"},{"issue":"3","key":"12_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"Ruzzo, W.: On uniform circuit complexity. J. of Computer System Science\u00a022(3), 365\u2013383 (1981)","journal-title":"J. of Computer System Science"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T23:02:35Z","timestamp":1738191755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_12","relation":{},"subject":[]}}