Memorias de investigación
Artículos en revistas:
Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
Año:2008
Áreas de investigación
  • Lenguaje de programación
Datos
Descripción
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.
Internacional
Si
JCR del ISI
No
Título de la revista
Logic Programming
ISSN
03029743
Factor de impacto JCR
0
Información de impacto
Volumen
5079/2008
DOI
10.1007/978-3-540-69166-2_15
Número de revista
5078
Desde la página
221
Hasta la página
237
Mes
JULIO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Elvira Albert Albiol UPM
  • Autor: Samir Genaim . UPM
  • Autor: Alvaro German Puebla Sanchez UPM
  • Autor: Purificación Arenas Sánchez UPM
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • 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