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
Termination and Cost Analysis: Complexity and Precision Issues
Technical University of Madrid.ORCID iD: 0000-0002-4872-1208
2012 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The research in this thesis is related to static cost and termination analysis.Cost analysis aims at estimating the amount of resources that a given programconsumes during the execution, and termination analysis aims at proving thatthe execution of a given program will eventually terminate. These analyses arestrongly related, indeed cost analysis techniques heavily rely on techniques developedfor termination analysis. Precision, scalability, and applicability are essentialin static analysis in general. Precision is related to the quality of the inferredresults, scalability to the size of programs that can be analyzed, and applicabilityto the class of programs that can be handled by the analysis (independently fromprecision and scalability issues). This thesis addresses these aspects in the contextof cost and termination analysis, from both practical and theoretical perspectives.For cost analysis, we concentrate on the problem of solving cost relations (aform of recurrence relations) into closed-form upper and lower bounds, which isthe heart of most modern cost analyzers, and also where most of the precision andapplicability limitations can be found. We develop tools, and their underlyingtheoretical foundations, for solving cost relations that overcome the limitations ofexisting approaches, and demonstrate superiority in both precision and applicability.A unique feature of our techniques is the ability to smoothly handle bothlower and upper bounds, by reversing the corresponding notions in the underlyingtheory. For termination analysis, we study the hardness of the problem ofdeciding termination for a specic form of simple loops that arise in the context ofcost analysis. This study gives a better understanding of the (theoretical) limitsof scalability and applicability for both termination and cost analysis.

Place, publisher, year, edition, pages
School of Computer Science, Technical University of Madrid , 2012. , 152 p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-23902OAI: oai:DiVA.org:mdh-23902DiVA: diva2:682331
Supervisors
Available from: 2013-12-30 Created: 2013-12-20 Last updated: 2013-12-30Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Masud, Abu Naser
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Total: 4497 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