Asymptotic Resource Usage Bounds

Albert Albiol, Elvira and Alonso, D. and Arenas Sánchez, Purificación and Genaim, Samir and Puebla Sánchez, Alvaro Germán (2009). Asymptotic Resource Usage Bounds. In: "7th Asian Symposium on Programming Languages and Systems, APLAS '09", 14/12/2009 - 16/12/2009, Seoul, Korea. ISBN 978-3-642-10671-2.


Title: Asymptotic Resource Usage Bounds
  • Albert Albiol, Elvira
  • Alonso, D.
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Item Type: Presentation at Congress or Conference (Article)
Event Title: 7th Asian Symposium on Programming Languages and Systems, APLAS '09
Event Dates: 14/12/2009 - 16/12/2009
Event Location: Seoul, Korea
Title of Book: Programming Languages and Systems. Proceedings of the 7th Asian Symposium, APLAS '09
Date: 2009
ISBN: 978-3-642-10671-2
Volume: 5904
Faculty: Facultad de Informática (UPM)
Department: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (245kB) | Preview


When describing the resource usage of a program, it is usual to talk in asymptotic terms, such as the well-known “big O” notation, whereby we focus on the behaviour of the program for large input data and make a rough approximation by considering as equivalent programs whose resource usage grows at the same rate. Motivated by the existence of non-asymptotic resource usage analyzers, in this paper, we develop a novel transformation from a non-asymptotic cost function (which can be produced by multiple resource analyzers) into its asymptotic form. Our transformation aims at producing tight asymptotic forms which do not contain redundant subexpressions (i.e., expressions asymptotically subsumed by others). Interestingly, we integrate our transformation at the heart of a cost analyzer to generate asymptotic upper bounds without having to first compute their non-asymptotic counterparts. Our experimental results show that, while non-asymptotic cost functions become very complex, their asymptotic forms are much more compact and manageable. This is essential to improve scalability and to enable the application of cost analysis in resource-aware verification/certification.

More information

Item ID: 5703
DC Identifier:
OAI Identifier:
Deposited by: Memoria Investigacion
Deposited on: 12 Jan 2011 09:51
Last Modified: 20 Apr 2016 14:26
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM