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
More precise yet widely applicable cost analysis
Complutense University of Madrid.
Complutense University of Madrid.
Technical University of Madrid.ORCID iD: 0000-0002-4872-1208
2011 (English)In: Lecture Notes in Computer Science, vol. 6538, Springer, 2011, Vol. 6538, p. 38-53Chapter in book (Refereed)
Abstract [en]

Cost analysis aims at determining the amount of resources required to run a program in terms of its input data sizes. Automatically inferring precise bounds, while at the same time being able to handle a wide class of programs, is a main challenge in cost analysis. (1) Existing methods which rely on computer algebra systems (CAS) to solve the obtained cost recurrence equations (CR) are very precise when applicable, but handle a very restricted class of CR. (2) Specific solvers developed for CR tend to sacrifice accuracy for wider applicability. In this paper, we present a novel approach to inferring precise upper and lower bounds on CR which, when compared to (1), is strictly more widely applicable while precision is kept and when compared to (2), is in practice more precise (obtaining even tighter complexity orders), keeps wide applicability and, besides, can be applied to obtain useful lower bounds as well. The main novelty is that we are able to accurately bound the worst-case/best-case cost of each iteration of the program loops and, then, by summing the resulting sequences, we achieve very precise upper/lower bounds. 

Place, publisher, year, edition, pages
Springer, 2011. Vol. 6538, p. 38-53
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6538
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-23901DOI: 10.1007/978-3-642-18275-4_5ISBN: 9783642182747 (print)OAI: oai:DiVA.org:mdh-23901DiVA, id: diva2:682342
Note

12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011; Austin, TX; United States; 23 January 2011 through 25 January 2011

Available from: 2013-12-27 Created: 2013-12-20 Last updated: 2014-01-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Masud, Abu Naser

Search in DiVA

By author/editor
Masud, Abu Naser
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 14 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