Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
Year:2008
Research Areas
  • Programming language
Information
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.
International
Si
JCR
No
Title
Logic Programming
ISBN
03029743
Impact factor JCR
0
Impact info
Volume
5079/2008
10.1007/978-3-540-69166-2_15
Journal number
5078
From page
221
To page
237
Month
JULIO
Ranking
Participants
  • Autor: Elvira Albert Albiol (UPM)
  • Autor: Samir Genaim . (UPM)
  • Autor: Alvaro German Puebla Sanchez (UPM)
  • Autor: Purificación Arenas Sánchez (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Computación lógica, Lenguajes, Implementación y Paralelismo (CLIP)
  • Departamento: Inteligencia Artificial
  • Departamento: Lenguajes y Sistemas Informáticos e Ingeniería de Software
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)