{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:06Z","timestamp":1742914086770,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642224379"},{"type":"electronic","value":"9783642224386"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22438-6_32","type":"book-chapter","created":{"date-parts":[[2011,7,18]],"date-time":"2011-07-18T22:21:44Z","timestamp":1311027704000},"page":"422-438","source":"Crossref","is-referenced-by-count":8,"title":["A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems"],"prefix":"10.1007","author":[{"given":"Lars","family":"Noschinski","sequence":"first","affiliation":[]},{"given":"Fabian","family":"Emmes","sequence":"additional","affiliation":[]},{"given":"J\u00fcrgen","family":"Giesl","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0304-3975(99)00207-8","volume":"236","author":"T. Arts","year":"2000","unstructured":"Arts, T., Giesl, J.: Termination of term rewriting using dependency pairs. Theoretical Computer Science\u00a0236, 133\u2013178 (2000)","journal-title":"Theoretical Computer Science"},{"key":"32_CR2","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-71070-7_10","volume-title":"Automated Reasoning","author":"M. Avanzini","year":"2008","unstructured":"Avanzini, M., Moser, G., Schnabl, A.: Automated Implicit Computational Complexity Analysis (System Description). In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol.\u00a05195, pp. 132\u2013138. Springer, Heidelberg (2008)"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-02348-4_4","volume-title":"Rewriting Techniques and Applications","author":"M. Avanzini","year":"2009","unstructured":"Avanzini, M., Moser, G.: Dependency Pairs and Polynomial Path Orders. In: Treinen, R. (ed.) RTA 2009. LNCS, vol.\u00a05595, pp. 48\u201362. Springer, Heidelberg (2009)"},{"key":"32_CR4","unstructured":"Avanzini, M., Moser, G.: Closing the gap between runtime complexity and polytime computability. In: Proc. RTA\u00a02010. LIPIcs, vol.\u00a06, pp. 33\u201348 (2010)"},{"key":"32_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-12251-4_19","volume-title":"Functional and Logic Programming","author":"M. Avanzini","year":"2010","unstructured":"Avanzini, M., Moser, G.: Complexity Analysis by Graph Rewriting. In: Blume, M., Kobayashi, N., Vidal, G. (eds.) FLOPS 2010. LNCS, vol.\u00a06009, pp. 257\u2013271. Springer, Heidelberg (2010)"},{"key":"32_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752","volume-title":"Term Rewriting and All That","author":"F. Baader","year":"1998","unstructured":"Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge U. Pr., Cambridge (1998)"},{"issue":"1","key":"32_CR7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1017\/S0956796800003877","volume":"11","author":"G. Bonfante","year":"2001","unstructured":"Bonfante, G., Cichon, A., Marion, J.-Y., Touzet, H.: Algorithms with polynomial interpretation termination proof. J. Functional Programming\u00a011(1), 33\u201353 (2001)","journal-title":"J. Functional Programming"},{"issue":"2-3","key":"32_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10817-007-9087-9","volume":"40","author":"J. Endrullis","year":"2008","unstructured":"Endrullis, J., Waldmann, J., Zantema, H.: Matrix interpretations for proving termination of term rewriting. J. Automated Reasoning\u00a040(2-3), 195\u2013220 (2008)","journal-title":"J. Automated Reasoning"},{"issue":"4","key":"32_CR9","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1016\/j.ic.2006.08.007","volume":"205","author":"A. Geser","year":"2007","unstructured":"Geser, A., Hofbauer, D., Waldmann, J., Zantema, H.: On tree automata that certify termination of left-linear term rewriting systems. Information and Computation\u00a0205(4), 512\u2013534 (2007)","journal-title":"Information and Computation"},{"key":"32_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-540-32275-7_21","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"J. Giesl","year":"2005","unstructured":"Giesl, J., Thiemann, R., Schneider-Kamp, P.: The Dependency Pair Framework: Combining Techniques for Automated Termination Proofs. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 301\u2013331. Springer, Heidelberg (2005)"},{"issue":"3","key":"32_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10817-006-9057-7","volume":"37","author":"J. Giesl","year":"2006","unstructured":"Giesl, J., Thiemann, R., Schneider-Kamp, P., Falke, S.: Mechanizing and improving dependency pairs. Journal of Automated Reasoning\u00a037(3), 155\u2013203 (2006)","journal-title":"Journal of Automated Reasoning"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"Giesl, J., Raffelsieper, M., Schneider-Kamp, P., Swiderski, S., Thiemann, R.: Automated termination proofs for Haskell by term rewriting. ACM Transactions on Programming Languages and Systems\u00a033(2) (2011)","DOI":"10.1145\/1890028.1890030"},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1145\/566385.566387","volume":"3","author":"R. Givan","year":"2002","unstructured":"Givan, R., McAllester, D.A.: Polynomial-time computation via local inference relations. ACM Transactions on Computational Logic\u00a03(4), 521\u2013541 (2002)","journal-title":"ACM Transactions on Computational Logic"},{"issue":"1,2","key":"32_CR14","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.ic.2004.10.004","volume":"199","author":"N. Hirokawa","year":"2005","unstructured":"Hirokawa, N., Middeldorp, A.: Automating the dependency pair method. Information and Computation\u00a0199(1,2), 172\u2013199 (2005)","journal-title":"Information and Computation"},{"key":"32_CR15","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-540-71070-7_32","volume-title":"Automated Reasoning","author":"N. Hirokawa","year":"2008","unstructured":"Hirokawa, N., Moser, G.: Automated Complexity Analysis Based on the Dependency Pair Method. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol.\u00a05195, pp. 364\u2013379. Springer, Heidelberg (2008)"},{"key":"32_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1007\/978-3-540-89439-1_45","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"N. Hirokawa","year":"2008","unstructured":"Hirokawa, N., Moser, G.: Complexity, Graphs, and the Dependency Pair Method. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol.\u00a05330, pp. 652\u2013666. Springer, Heidelberg (2008)"},{"key":"32_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-51081-8_107","volume-title":"Rewriting Techniques and Applications","author":"D. Hofbauer","year":"1989","unstructured":"Hofbauer, D., Lautemann, C.: Termination proofs and the length of derivations. In: Dershowitz, N. (ed.) RTA 1989. LNCS, vol.\u00a0355, pp. 167\u2013177. Springer, Heidelberg (1989)"},{"key":"32_CR18","first-page":"464","volume-title":"Proc. LICS\u00a01999","author":"M. Hofmann","year":"1999","unstructured":"Hofmann, M.: Linear types and non-size-increasing polynomial time computation. In: Proc. LICS\u00a01999, pp. 464\u2013473. IEEE Press, Los Alamitos (1999)"},{"issue":"2","key":"32_CR19","first-page":"357","volume":"19","author":"A. Koprowski","year":"2009","unstructured":"Koprowski, A., Waldmann, J.: Max\/plus tree automata for termination of term rewriting. Acta Cybernetica\u00a019(2), 357\u2013392 (2009)","journal-title":"Acta Cybernetica"},{"key":"32_CR20","first-page":"79","volume-title":"Proc. PPDP\u00a02008","author":"J.-Y. Marion","year":"2008","unstructured":"Marion, J.-Y., P\u00e9choux, R.: Characterizations of polynomial complexity classes with a better intensionality. In: Proc. PPDP\u00a02008, pp. 79\u201388. ACM Press, New York (2008)"},{"key":"32_CR21","unstructured":"Moser, G., Schnabl, A., Waldmann, J.: Complexity analysis of term rewriting based on matrix and context dependent interpretations. In: Proc. FSTTCS\u00a02008. LIPIcs, vol.\u00a02, pp. 304\u2013315 (2008)"},{"key":"32_CR22","unstructured":"Moser, G.: Personal communication (2010)"},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1007\/978-3-642-16242-8_39","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"F. Neurauter","year":"2010","unstructured":"Neurauter, F., Zankl, H., Middeldorp, A.: Revisiting Matrix Interpretations for Polynomial Derivational Complexity of Term Rewriting. In: Ferm\u00fcller, C.G., Voronkov, A. (eds.) LPAR-17. LNCS, vol.\u00a06397, pp. 550\u2013564. Springer, Heidelberg (2010)"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Noschinski, L., Emmes, F., Giesl, J.: A dependency pair framework for innermost complexity analysis of term rewrite systems. Technical Report AIB-2011-03, RWTH Aachen (2011), http:\/\/aib.informatik.rwth-aachen.de","DOI":"10.1007\/978-3-642-22438-6_32"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Otto, C., Brockschmidt, M., von Essen, C., Giesl, J.: Automated termination analysis of Java Bytecode by term rewriting. In: Proc. RTA 2010. LIPIcs, vol.\u00a06, pp. 259\u2013276 (2010)","DOI":"10.1007\/978-3-642-17172-7_2"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Schneider-Kamp, P., Giesl, J., Str\u00f6der, T., Serebrenik, A., Thiemann, R.: Automated termination analysis for logic programs with cut. In: Proc. ICLP\u00a02010, Theory and Practice of Logic Programming, vol.10(4-6), pp. 365\u2013381 (2010)","DOI":"10.1017\/S1471068410000165"},{"key":"32_CR27","unstructured":"Waldmann, J.: Polynomially bounded matrix interpretations. In: Proc. RTA\u00a02010. LIPIcs, vol.\u00a06, pp. 357\u2013372 (2010)"},{"key":"32_CR28","unstructured":"Zankl, H., Korp, M.: Modular complexity analysis via relative complexity. In: Proc. RTA\u00a02010. LIPIcs, vol.\u00a06, pp. 385\u2013400 (2010)"}],"container-title":["Lecture Notes in Computer Science","Automated Deduction \u2013 CADE-23"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22438-6_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,28]],"date-time":"2021-11-28T08:13:59Z","timestamp":1638087239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22438-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642224379","9783642224386"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22438-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}