mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Inference of Resource Usage Upper and Lower Bounds
Complutense University of Madrid.
Complutense University of Madrid.
Technical University of Madrid.ORCID iD: 0000-0002-4872-1208
2013 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, Vol. 14, no 3, Article number 22- p.Article in journal (Refereed) Published
Abstract [en]

Cost analysis 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 loops 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 upper and lower bounds from cost relations. These relations are an extended form of standard recurrence equations 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 worst-case and best-case deterministic one-argument recurrence relations. The solution of each recursive relation provides a preciseupper-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.

Place, publisher, year, edition, pages
ACM Press, 2013. Vol. 14, no 3, Article number 22- p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-23899DOI: 10.1145/2499937.2499943ISI: 000323892900006Scopus ID: 2-s2.0-84883620006OAI: oai:DiVA.org:mdh-23899DiVA: diva2:682328
Available from: 2013-12-27 Created: 2013-12-20 Last updated: 2014-06-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Masud, Abu Naser
In the same journal
ACM Transactions on Computational Logic
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 31 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf