|
 ABSTRACT
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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
[1]
|
Adachi, A., Kasai, T. and Moriya, E., A theoretical study of the time analysis of programs. In: Becvár, J. (Ed.), Lecture Notes in Computer Science, volume 74. Springer. pp. 201-207.
|
| |
[2]
|
Albert, E., Arenas, P., Genaim, S., Puebla, G. and Zanardini, D., Cost Analysis of Java Bytecode. In: De Nicola, Rocco (Ed.), Lecture Notes in Computer Science, volume 4421. Springer. pp. 157-172.
|
 |
[3]
|
E. Albert , P. Arenas , S. Genaim , G. Puebla , D. Zanardini, Removing useless variables in cost analysis of Java bytecode, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
[doi> 10.1145/1363686.1363779]
|
| |
[4]
|
|
| |
[5]
|
|
| |
[6]
|
Aspinall, D., Gilmore, S., Hofmann, M., Sannella, D. and Stark, I., Mobile Resource Guarantees for Smart Devices. In: Barthe, G., Burdy, L., Huisman, M., Lanet, J.-L., Muntean, T. (Eds.), LNCS, volume 3362. Springer. pp. 1-27.
|
| |
[7]
|
R. Bagnara, A. Pescetti, A. Zaccagnini, and E. Zaffanella. PURRS: Towards computer algebra support for fully automatic worst-case complexity analysis. Technical report, 2005. arXiv:cs/0512056 available from http://arxiv.org/
|
| |
[8]
|
|
| |
[9]
|
Chander, Ajay, Espinosa, David, Islam, Nayeem, Lee, Peter and Necula, George C., Enforcing resource bounds via static verification of dynamic checks. In: LNCS, number 3444. Springer-Verlag. pp. 311-325.
|
| |
[10].
|
|
| |
[11]
|
|
| |
[12]
|
Debray, S.K. and Lin, N.-W., Automatic complexity analysis for logic programs. In: Eighth International Conference on Logic Programming, MIT Press. pp. 599-613.
|
| |
[13]
|
|
| |
[14]
|
Hill, Patricia M., Payet, Etienne and Spoto, Fausto, Path-length analysis of object-oriented programs. Electronic Notes in Theoretical Computer Science.
|
| |
[15]
|
Jouannaud, J. and Xu, W., Automatic Complexity Analysis for Programs Extracted from Coq Proof. ENTCS.
|
| |
[16]
|
|
| |
[17]
|
Navas, J., Mera, E., López-García, P. and Hermenegildo, M., User-Definable Resource Bounds Analysis for Logic Programs. In: LNCS, volume 4670. Springer-Verlag. pp. 348-363.
|
| |
[18]
|
|
| |
[19]
|
Sands, D., A naïve time analysis and its theory of cost equivalence. J. Log. Comput. v5 i4.
|
| |
[20]
|
F. Spoto, P. M. Hill, and E. Payet. Path-length analysis for object-oriented programs. In Proc. International Workshop on Emerging Applications of Abstract Interpretation (EAAI), 2006
|
| |
[21]
|
|
| |
[22]
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
