Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis

Albert Albiol, Elvira; Arenas Sánchez, Purificación; Genaim, Samir y 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.

Descripción

Título: Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
Autor/es:
  • Albert Albiol, Elvira
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Tipo de Documento: Artículo
Título de Revista/Publicación: Lecture Notes in Computer Science
Fecha: Julio 2008
Volumen: 5079
Materias:
Palabras Clave Informales: Automatic cost analysis, recurrence relations (RRs), upper bounds, inference of ranking functions,loop invariants, partial evaluation.
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 (596kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 2904
Identificador DC: http://oa.upm.es/2904/
Identificador OAI: oai:oa.upm.es:2904
Identificador DOI: 10.1007/978-3-540-69166-2_15
URL Oficial: http://www.springer.com/computer/lncs?SGWID=0-164-0-0-0
Depositado por: Memoria Investigacion
Depositado el: 26 Abr 2010 09:12
Ultima Modificación: 20 Abr 2016 12:31
  • 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