{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:48:37Z","timestamp":1762458517286},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540659228"},{"type":"electronic","value":"9783540488552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/10703163_25","type":"book-chapter","created":{"date-parts":[[2006,10,9]],"date-time":"2006-10-09T18:15:50Z","timestamp":1160417750000},"page":"372-384","source":"Crossref","is-referenced-by-count":6,"title":["Complexity Classes and Rewrite Systems with Polynomial Interpretation"],"prefix":"10.1007","author":[{"given":"G.","family":"Bonfante","sequence":"first","affiliation":[]},{"given":"A.","family":"Cichon","sequence":"additional","affiliation":[]},{"given":"J. Y","family":"Marion","sequence":"additional","affiliation":[]},{"given":"H.","family":"Touzet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","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 polytime functions. Computational Complexity\u00a02, 97\u2013110 (1992)","journal-title":"Computational Complexity"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0167-6423(87)90030-X","volume":"9","author":"A. Ben Cherifa","year":"1987","unstructured":"Ben Cherifa, A., Lescanne, P.: Termination of rewriting systems by polynomial interpretations and its implementation. Science of computer Programming\u00a09, 131\u2013159 (1987)","journal-title":"Science of computer Programming"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/3-540-55602-8_161","volume-title":"Automated Deduction - CADE-11","author":"E.A. Cichon","year":"1992","unstructured":"Cichon, E.A., Lescanne, P.: Polynomial interpretations and the complexity of algorithms. In: Kapur, D. (ed.) CADE 1992. LNCS, vol.\u00a0607, pp. 139\u2013147. Springer, Heidelberg (1992)"},{"key":"25_CR4","first-page":"24","volume-title":"Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science","author":"A. Cobham","year":"1962","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pp. 24\u201330. North-Holland, Amsterdam (1962)"},{"key":"25_CR5","unstructured":"Dershowitz, N., Jouannaud, J.P.: Rewrite systems. Handbook of Theoretical Computer Science, vol.\u00a0B. North-Holland, Amsterdam"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","first-page":"427","volume-title":"Rewriting Techniques and Applications","author":"J. Giesl","year":"1995","unstructured":"Giesl, J.: Generating polynomial orderings for termination proofs. In: Hsiang, J. (ed.) RTA 1995. LNCS, vol.\u00a0914, pp. 427\u2013431. Springer, Heidelberg (1995)"},{"key":"25_CR7","first-page":"210","volume-title":"Twenty Fourth Symposium on Foundations of Computer Science","author":"Y. Gurevich","year":"1983","unstructured":"Gurevich, Y.: Algebras of feasible functions. In: Twenty Fourth Symposium on Foundations of Computer Science, pp. 210\u2013214. IEEE Computer Society Press, Los Alamitos (1983)"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Hofbauer, D., Lautemann, C.: Termination proofs and the length of derivations. In: RTA-1988. LNCS, vol.\u00a0355","DOI":"10.1007\/3-540-51081-8_107"},{"key":"25_CR9","unstructured":"Lankford, D.S.: On proving term rewriting systems are Noetherien. Technical Report Memo MTP-3, louisiana Technical University, Ruston, LA (1979)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Leivant, D.: Predicative recurrence and computational complexity I: Word recurrence and poly-time. In: Clote, P., Remmel, J. (eds.) Feasible Mathematrics II, Birkhauser-Boston (1994)","DOI":"10.1007\/978-1-4612-2566-9_11"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10703163_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T15:16:12Z","timestamp":1555859772000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10703163_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540659228","9783540488552"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/10703163_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]}}}