Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis

Albert Albiol, Elvira and Arenas Sánchez, Purificación and Genaim, Samir and Puebla Sánchez, Alvaro Germán (2008). Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis. "Lecture Notes in Computer Science", v. 5079 ; pp. 221-237. ISSN 0302-9743. https://doi.org/10.1007/978-3-540-69166-2_15.

Description

Title: Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
Author/s:
  • Albert Albiol, Elvira
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Item Type: Article
Título de Revista/Publicación: Lecture Notes in Computer Science
Date: July 2008
Volume: 5079
Subjects:
Freetext Keywords: Automatic cost analysis, recurrence relations (RRs), upper bounds, inference of ranking functions,loop invariants, partial evaluation.
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

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

Abstract

The classical approach to automatic cost analysis consists of two phases. Given a program and some measure of cost, we first produce recurrence relations (RRs) which capture the cost of our program in terms of the size of its input data. Second, we convert such RRs into closed form (i.e., without recurrences). Whereas the first phase has received considerable attention, with a number of cost analyses available for a variety of programming languages, the second phase has received comparatively little attention. In this paper we first study the features of RRs generated by automatic cost analysis and discuss why existing computer algebra systems are not appropriate for automatically obtaining closed form solutions nor upper bounds of them. Then we present, to our knowledge, the first practical framework for the fully automatic generation of reasonably accurate upper bounds of RRs originating from cost analysis of a wide range of programs. It is based on the inference of ranking functions and loop invariants and on partial evaluation.

More information

Item ID: 2904
DC Identifier: http://oa.upm.es/2904/
OAI Identifier: oai:oa.upm.es:2904
DOI: 10.1007/978-3-540-69166-2_15
Official URL: http://www.springer.com/computer/lncs?SGWID=0-164-0-0-0
Deposited by: Memoria Investigacion
Deposited on: 26 Apr 2010 09:12
Last Modified: 20 Apr 2016 12:31
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM