Interpolation-based height analysis for improving a recurrence solver

Autor:	Montenegro, M., Shkaravska, O., Eekelen, M.C.J.D. van, Pena, R., Eekelen, M. Van
Přispěvatelé:	Pena, R., Eekelen, M. Van, Shkaravska, O.
Rok vydání:	2012
Předmět:	Polynomial Recurrence relation Degree (graph theory) Computer science Java bytecode Lecture Notes in Computer Science Solver Digital Security computer Algorithm Polynomial interpolation Interpolation computer.programming_language
Zdroj:	Pena, R.; Eekelen, M. Van; Shkaravska, O. (ed.), Foundational and Practical Aspects of Resource Analysis, Second International Workshop, FOPARA 2011 : Madrid, Spain, May 19, 2011, Revised Selected Papers, pp. 36-53 Lecture Notes in Computer Science ; 7177, 36-53. Berlin : Springer STARTPAGE=36;ENDPAGE=53;TITLE=Lecture Notes in Computer Science ; 7177 Foundational and Practical Aspects of Resource Analysis ISBN: 9783642324949 FOPARA
DOI:	10.1007/978-3-642-32495-6_3
Popis:	The COSTA system infers resource consumption bounds from Java bytecode using an internal recurrence solver PUBS. This paper suggests an improvement of the COSTA system, such that it can solve a larger number of recurrences. The idea is to replace one of its static analyses, the ranking function analysis, by another kind of analysis, height analysis, in such a way that polynomial bounds of any degree may be inferred instead of just linear expressions. The work can be seen as an application of some polynomial interpolation techniques used by some of the authors in prior analyses. Finding a way to choose proper test nodes is the key to the solution presented in this paper.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2eaf2d09a34455c6cfbdcbc0d570f3b2 https://doi.org/10.1007/978-3-642-32495-6_3 Zobrazit plný text záznamu