{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T12:47:51Z","timestamp":1788871671899,"version":"build-2803163510"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["TIN-2008-05624, PRI-AIBDE-2011-0900, UCM-BSCH-GR35\/10-A-910502"],"award-info":[{"award-number":["TIN-2008-05624, PRI-AIBDE-2011-0900, UCM-BSCH-GR35\/10-A-910502"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Madrid Regional Government","award":["S2009TIC-1465 PROMETIDOS-CM"],"award-info":[{"award-number":["S2009TIC-1465 PROMETIDOS-CM"]}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["ICT-231620 HATS"],"award-info":[{"award-number":["ICT-231620 HATS"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>\n                    <jats:italic>Cost analysis<\/jats:italic>\n                    aims at determining the amount of resources required to run a program in terms of its input data sizes. The most challenging step is to infer the cost of executing the\n                    <jats:italic>loops<\/jats:italic>\n                    in the program. This requires bounding the number of iterations of each loop and finding tight bounds for the cost of each of its iterations. This article presents a novel approach to infer\n                    <jats:italic>upper<\/jats:italic>\n                    and\n                    <jats:italic>lower<\/jats:italic>\n                    bounds from\n                    <jats:italic>cost relations<\/jats:italic>\n                    . These relations are an extended form of standard\n                    <jats:italic>recurrence equations<\/jats:italic>\n                    that can be nondeterministic, contain inexact size constraints and have multiple arguments that increase and\/or decrease. We propose novel techniques to automatically transform cost relations into\n                    <jats:italic>worst-case<\/jats:italic>\n                    and\n                    <jats:italic>best-case<\/jats:italic>\n                    deterministic one-argument recurrence relations. The solution of each recursive relation provides a precise upper-bound and lower-bound for executing a corresponding loop in the program. Importantly, since the approach is developed at the level of the cost equations, our techniques are programming language independent.\n                  <\/jats:p>","DOI":"10.1145\/2499937.2499943","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T07:57:11Z","timestamp":1378195031000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["On the Inference of Resource Usage Upper and Lower Bounds"],"prefix":"10.1145","volume":"14","author":[{"given":"Elvira","family":"Albert","sequence":"first","affiliation":[{"name":"Complutense University of Madrid, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samir","family":"Genaim","sequence":"additional","affiliation":[{"name":"Complutense University of Madrid, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abu Naser","family":"Masud","sequence":"additional","affiliation":[{"name":"Technical University of Madrid, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Adachi A. Kasai T. and \n      \n      \n      Moriya E\n      \n  \n  . \n  1979\n  . A theoretical study of the time analysis of programs. In Proceedings of the 8th Symposium on Mathematical Foundations of Computer Science. J. Becv\u00e1r Ed. Lecture Notes in Computer Science Series vol. \n  74 Springer 201--207.  Adachi A. Kasai T. and Moriya E. 1979. A theoretical study of the time analysis of programs. In Proceedings of the 8th Symposium on Mathematical Foundations of Computer Science . J. Becv\u00e1r Ed. Lecture Notes in Computer Science Series vol. 74 Springer 201--207.","DOI":"10.1007\/3-540-09526-8_16"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03829-7_9"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Comparing cost functions in resource analysis. In Proceedings of the 1st International Workshop on Foundational and Practical Aspects of Resource Analysis (FOPARA\u201909)","volume":"6234","author":"Albert E.","year":"2010","journal-title":"Lecture Notes in Computer Science Series"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25318-8_19"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-010-9174-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967677.1967681"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Albert E. Genaim S. and \n      \n      \n      Masud A. N\n      \n  \n  . \n  2011\n  d. More precise yet widely applicable cost analysis. In Proceedings of the 12th Verification Model Checking and Abstract Interpretation (VMCAI\u201911). R. Jhala and D. Schmidt Eds. Lecture Notes in Computer Science Series vol. \n  6538 Springer Verlag 38--53.   Albert E. Genaim S. and Masud A. N. 2011d. More precise yet widely applicable cost analysis. In Proceedings of the 12th Verification Model Checking and Abstract Interpretation (VMCAI\u201911) . R. Jhala and D. Schmidt Eds. Lecture Notes in Computer Science Series vol. 6538 Springer Verlag 38--53.","DOI":"10.1007\/978-3-642-18275-4_5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33125-1_27"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"e_1_2_1_11_1","unstructured":"Bagnara R. Zaccagnini A. and Zolo T. 2003. The automatic solution of recurrence relations. I. Linear recurrences of finite order with constant coefficients. Quaderno 334 Dipartimento di Matematica Universit\u00e0 di Parma Italy. http:\/\/www.cs.unipr.it\/Publications\/.  Bagnara R. Zaccagnini A. and Zolo T. 2003. The automatic solution of recurrence relations. I. Linear recurrences of finite order with constant coefficients. Quaderno 334 Dipartimento di Matematica Universit\u00e0 di Parma Italy. http:\/\/www.cs.unipr.it\/Publications\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.022"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355751"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512770"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325716"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/161468.161472"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Everest G. van der Poorten A. Shparlinski I. and Ward T. 2003. Recurrence Sequences. American Mathematical Society Providence RI.  Everest G. van der Poorten A. Shparlinski I. and Ward T. 2003. Recurrence Sequences . American Mathematical Society Providence RI.","DOI":"10.1090\/surv\/104"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.75.1.40"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480898"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604148"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926427"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Federation for Information Processing. 569--574","author":"Kowalski R. A.","year":"1974"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/42190.42347"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111542.1111563"},{"key":"e_1_2_1_27_1","unstructured":"Maxima 2009. Maxima a Computer Algebra System. http:\/\/maxima.sourceforge.net.  Maxima 2009. Maxima a Computer Algebra System. http:\/\/maxima.sourceforge.net."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 23rd International Conference on Logic Programming (ICLP\u201907)","volume":"4670","author":"Navas J."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99381"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.4.495"},{"key":"e_1_2_1_31_1","unstructured":"Schrijver A. 1986. Theory of Linear and Integer Programming. John Wiley & Sons Inc.   Schrijver A. 1986. Theory of Linear and Integer Programming . John Wiley & Sons Inc."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73571"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361016"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499943","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499937.2499943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:34:00Z","timestamp":1750217640000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2499937.2499943"],"URL":"https:\/\/doi.org\/10.1145\/2499937.2499943","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}