A practical comparator of cost functions and its applications
| Autor: | Puri Arenas, Samir Genaim, Germán Puebla, Elvira Albert |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Spectrum analyzer
Focus (computing) Mathematical problem Source code Comparator Computer science business.industry Small number media_common.quotation_subject 0102 computer and information sciences 02 engineering and technology 01 natural sciences Software Computer engineering 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering business Algorithm Program synthesis media_common |
| Zdroj: | E-Prints Complutense. Archivo Institucional de la UCM instname E-Prints Complutense: Archivo Institucional de la UCM Universidad Complutense de Madrid |
| Popis: | Automatic cost analysis has significantly advanced in the last few years. Nowadays, a number of cost analyzers exist which automatically produce upper- and/or lower-bounds on the amount of resources required to execute a program. Cost analysis has a number of important applications such as resource-usage verification and program synthesis and optimization. For such applications to be successful, it is not sufficient to have automatic cost analysis. It is also required to have automated means for handling the analysis results, which are in the form of Cost Functions (CFs for short) i.e., non-recursive expressions composed of a relatively small number of types of basic expressions. In particular, we need automated means for comparing CFs in order to prove that a CF is smaller than or equal to another one for all input values of interest. General function comparison is a hard mathematical problem. Rather than attacking the general problem, in this work we focus on comparing CFs by exploiting their syntactic properties and we present, to the best of our knowledge, the first practical CF comparator which opens the door to fully automated applications of cost analysis. We have implemented the comparator and made its source code available online, so that any cost analyzer can use it. We present a practical comparator of cost functions for realistic programs.We handle max , min , and nat operators which appear in upper and lower bounds.We present a number of applications where the comparator is essential.The comparator is implemented and available online as free software. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|