2008 | OriginalPaper | Buchkapitel
Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
verfasst von : Elvira Albert, Puri Arenas, Samir Genaim, Germán Puebla
Erschienen in: Static Analysis
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.