Asymptotic Resource Usage Bounds

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

Descripción

Título: Asymptotic Resource Usage Bounds
Autor/es:
  • Albert Albiol, Elvira
  • Alonso, D.
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 7th Asian Symposium on Programming Languages and Systems, APLAS '09
Fechas del Evento: 14/12/2009 - 16/12/2009
Lugar del Evento: Seoul, Korea
Título del Libro: Programming Languages and Systems. Proceedings of the 7th Asian Symposium, APLAS '09
Fecha: 2009
ISBN: 978-3-642-10671-2
Volumen: 5904
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (245kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 5703
Identificador DC: http://oa.upm.es/5703/
Identificador OAI: oai:oa.upm.es:5703
URL Oficial: http://www.springer.com/computer/swe/book/978-3-642-10671-2
Depositado por: Memoria Investigacion
Depositado el: 12 Ene 2011 09:51
Ultima Modificación: 20 Abr 2016 14:26
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM