Cost Relation Systems: A Language-Independent Target Language for Cost Analysis
| Autor: | Elvira Albert, Puri Arenas, Samir Genaim, Germán Puebla |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
General Computer Science
Relation (database) Computer science Programming language Static Analysis 020207 software engineering Java bytecode 0102 computer and information sciences 02 engineering and technology Complexity Static analysis computer.software_genre 01 natural sciences Cost Analysis Resource Usage Theoretical Computer Science Prolog Perspective (geometry) 010201 computation theory & mathematics Order (exchange) 0202 electrical engineering electronic engineering information engineering Haskell computer computer.programming_language Computer Science(all) |
| Zdroj: | Electronic Notes in Theoretical Computer Science. 248:31-46 |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2009.07.057 |
| Popis: | Cost analysis aims at obtaining information about the execution cost of programs. This paper studies cost relation systems (CRSs): the sets of recursive equations used in cost analysis in order to capture the execution cost of programs in terms of the size of their input arguments. We investigate the notion of CRS from a general perspective which is independent of the particular cost analysis framework. Our main contributions are: we provide a formal definition of execution cost and of CRS which is not tied to a particular programming language; we present the notion of sound CRS, i.e., which correctly approximates the cost of the corresponding program; we identify the differences with recurrence relation systems, its possible applications and the new challenges that they bring about. Our general framework is illustrated by instantiating it to cost analysis of Java bytecode, Haskell, and Prolog. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect