{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:07:54Z","timestamp":1760044074895,"version":"3.41.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240114"},{"type":"electronic","value":"9783319240121"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-24012-1_1","type":"book-chapter","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T18:01:22Z","timestamp":1444154482000},"page":"1-15","source":"Crossref","is-referenced-by-count":3,"title":["Automatic Inference of Loop Complexity Through Polynomial Interpolation"],"prefix":"10.1007","author":[{"given":"Francisco","family":"Demonti\u00ea","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junio","family":"Cezar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mariza","family":"Bigonha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederico","family":"Campos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"Magno Quint\u00e3o Pereira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,15]]},"reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.ipl.2014.08.008","volume":"115","author":"PRO Alves","year":"2015","unstructured":"Alves, P.R.O., Rodrigues, R.E., de Souza, R.M., Pereira, F.M.Q.: A case for a fast trip count predictor. Inf. Process. Lett. 115(2), 146\u2013150 (2015)","journal-title":"Inf. Process. Lett."},{"key":"1_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811432","volume-title":"Modern Compiler Implementation in Java","author":"AW Appel","year":"2002","unstructured":"Appel, A.W., Palsberg, J.: Modern Compiler Implementation in Java, 2nd edn. Cambridge University Press, Cambridge (2002)","edition":"2"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Che, S., Boyer, M., Meng, J., Tarjan, D., Sheaffer, J.W., Lee, S.-H., Skadron, K.: Rodinia: a benchmark suite for heterogeneous computing. In: IISWC, pp. 44\u201354. IEEE (2009)","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Coppa, E., Demetrescu, C., Finocchi, I.: Input-sensitive profiling. In: PLDI. ACM (2012)","DOI":"10.1145\/2254064.2254076"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Danielsson, N.A.: Lightweight semiformal time complexity analysis for purely functional data structures. In: POPL, pp. 133\u2013144. ACM (2008)","DOI":"10.1145\/1328897.1328457"},{"issue":"5","key":"1_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1145\/161468.161472","volume":"15","author":"SK Debray","year":"1993","unstructured":"Debray, S.K., Lin, N.-W.: Cost analysis of logic programs. ACM Trans. Program. Lang. Syst. 15(5), 826\u2013875 (1993)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"3","key":"1_CR8","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/24039.24041","volume":"9","author":"J Ferrante","year":"1987","unstructured":"Ferrante, J., Ottenstein, K.J., Warren, J.D.: The program dependence graph and its use in optimization. TOPLAS 9(3), 319\u2013349 (1987)","journal-title":"TOPLAS"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Goldsmith, S.F., Aiken, A.S., Wilkerson, D.S.: Measuring empirical computational complexity. In: FSE, pp. 395\u2013404. ACM (2007)","DOI":"10.1145\/1287624.1287681"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Graham, S.L., Kessler, P.B., McKusick, M.K.: gprof: a call graph execution profiler (with retrospective). In: Best of PLDI, pp. 49\u201357 (1982)","DOI":"10.1145\/800230.806987"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-70545-1_35","volume-title":"Computer Aided Verification","author":"BS Gulavani","year":"2008","unstructured":"Gulavani, B.S., Gulwani, S.: A numerical abstract domain based on expression abstraction and max operator with application in timing analysis. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 370\u2013384. Springer, Heidelberg (2008)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Jain, S., Koskinen, E.: Control-flow refinement and progress invariants for bound analysis. In: PLDI, pp. 375\u2013385. ACM (2009)","DOI":"10.1145\/1543135.1542518"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.: SPEED: precise and efficient static estimation of program computational complexity. In: POPL, pp. 127\u2013139. ACM (2009)","DOI":"10.1145\/1594834.1480898"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Lattner, C., Adve, V.S.: LLVM: a compilation framework for lifelong program analysis & transformation. In: CGO, pp. 75\u201388. IEEE (2004)","DOI":"10.1109\/CGO.2004.1281665"},{"issue":"2","key":"1_CR15","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/42190.42347","volume":"10","author":"D M\u00e9tayer Le","year":"1988","unstructured":"Le M\u00e9tayer, D.: Ace: an automatic complexity evaluator. ACM Trans. Program. Lang. Syst. 10(2), 248\u2013266 (1988)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-23702-7_27","volume-title":"Static Analysis","author":"D Monniaux","year":"2011","unstructured":"Monniaux, D., Gonnord, L.: Using bounded model checking to focus fixpoint iterations. In: Yahav, E. (ed.) Static Analysis. LNCS, vol. 6887, pp. 369\u2013385. Springer, Heidelberg (2011)"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Seward, J.: Valgrind: a framework for heavyweight dynamic binary instrumentation. In: PLDI, pp. 89\u2013100. ACM (2007)","DOI":"10.1145\/1273442.1250746"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Piccoli, G., Santos, H., Rodrigues, R., Pousa, C., Borin, E., Pereira, F.M.Q.: Compiler support for selective page migration in NUMA architectures. In: PACT, pp. 369\u2013380. ACM (2014)","DOI":"10.1145\/2628071.2628077"},{"key":"1_CR19","unstructured":"Pouchet, L.-N.: Polybench: the polyhedral benchmark suite (2012). http:\/\/www.cs.ucla.edu\/pouchet\/software\/polybench\/ . Accessed April 2015"},{"issue":"9","key":"1_CR20","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1145\/361002.361016","volume":"18","author":"B Wegbreit","year":"1975","unstructured":"Wegbreit, B.: Mechanical program analysis. Commun. ACM 18(9), 528\u2013539 (1975)","journal-title":"Commun. ACM"},{"key":"1_CR21","volume-title":"High Performance Compilers for Parallel Computing","author":"M Wolfe","year":"1996","unstructured":"Wolfe, M.: High Performance Compilers for Parallel Computing, 1st edn. Adison-Wesley, Redwood City (1996)","edition":"1"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Zaparanuks, D., Hauswirth, M.: Algorithmic profiling. In: PLDI, pp. 67\u201376. ACM (2012)","DOI":"10.1145\/2345156.2254074"}],"container-title":["Lecture Notes in Computer Science","Programming Languages"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24012-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:50:29Z","timestamp":1748645429000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24012-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240114","9783319240121"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24012-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}