Closed-Form Upper Bounds in Static Cost Analysis

Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)

Albert, E., Arenas, P., Codish, M., Genaim, S., Puebla, G., Zanardini, D.: Termination analysis of Java bytecode. In: 10th IFIP International Conference on Formal Methods for Open Object-based Distributed Systems (FMOODS’08). Lecture Notes in Computer Science, vol. 5051, pp. 2–18. Springer, Heidelberg (2008)

Albert, E., Arenas, P., Genaim, S., Herraiz, I., Puebla, G.: Comparing cost functions in resource analysis. In: 1st International Workshop on Foundational and Practical Aspects of Resource Analysis (FOPARA’09). Lecture Notes in Computer Science. Springer, Heidelberg (2009)

Albert, E., Arenas, P., Genaim, S., Puebla, G.: Automatic inference of upper bounds for recurrence relations in cost analysis. In: 15th International Symposium on Static Analysis (SAS’08). Lecture Notes in Computer Science, vol. 5079, pp. 221–237 (2008)

Albert, E., Arenas, P., Genaim, S., Puebla, G.: Cost relation systems: a language–independent target language for cost analysis. In: 8th Spanish Conference on Programming and Computer Languages (PROLE’08), vol. 17615 of Electronic Notes in Theoretical Computer Science. Elsevier (2008)

Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Cost analysis of Java bytecode. In: 16th European Symposium on Programming, (ESOP’07). Lecture Notes in Computer Science, vol. 4421, pp. 157–172. Springer (2007)

Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: COSTA: design and implementation of a cost and termination analyzer for Java bytecode. In: 6th International Symposioum on Formal Methods for Components and Objects (FMCO’08). Lecture Notes in Computer Science, no. 5382, pp. 113–133. Springer (2007)

Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Experiments in cost analysis of Java bytecode. In 2nd Workshop on Bytecode Semantics, Verification, Analysis and Transformation (BYTECODE’07), vol. 190, Issue 1 of Electronic Notes in Theoretical Computer Science. Elsevier (2007)

Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Resource usage analysis and its application to resource certification. In: 9th International School on Foundations of Security Analysis and Design (FOSAD’09). Lecture Notes in Computer Science, no. 5705, pp. 258–288. Springer (2009)

Albert, E., Genaim, S., Gómez-Zamalloa, M.: Heap space analysis of Java bytecode. In: 6th International Symposium on Memory Management (ISMM’07), pp. 105–116. ACM Press (2007)

Albert, E., Genaim, S., Gómez-Zamalloa, M.: Live Heap space analysis for languages with garbage collection. In: 8th International Symposium on Memory management (ISMM’09). ACM Press (2009)

Aspinall, D., Gilmore, S., Hofmann, M., Sannella, D., Stark, I.: Mobile resource guarantees for smart devices. In: Workshop on Construction and Analysis of Safe, Secure and Interoperable Smart Devices (CASSIS’04). Lecture Notes in Computer Science, vol. 3362, pp. 1–27. Springer (2005)

Bagnara, R., Hill, P.M., Zaffanella, E.: The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Program. 72(1–2), 3–21 (2008)

Bagnara, R., Pescetti, A., Zaccagnini, A., Zaffanella, E.: PURRS: towards computer algebra support for fully automatic worst-case complexity analysis. Technical report (2005). http://arXiv.org./abs/cs/0512056

Batchelder, P.M.: An introduction to linear difference equations. Dover Publications (1967)

Ben-Amram, A.M.: Size-change termination with difference constraints. ACM Trans. Program. Lang. Syst. 30(3), 31 (2008) (Article 16)

Ben-Amram, A.M., Jones, N.D., Kristiansen L.: Linear, polynomial or exponential? Complexity inference in polynomial time. In: Logic and Theory of Algorithms, 4th Conference on Computability in Europe, (CiE’08). Lecture Notes in Computer Science, vol. 5028, pp. 67–76. Springer (2008)

Benzinger, R.: Automated higher-order complexity analysis. Theor. Comp. Sci. 318(1–2), 79–103 (2004)

Bonfante, G., Marion, J.-Y., Moyen, J.-Y.: Quasi-interpretations and small space bounds. In: 16th International Conference on Rewriting Techniques and Applications (RTA’05). Lecture Notes in Computer Science, vol. 3467, pp. 150–164 (2005)

Braverman, M.: Termination of integer linear programs. In: 18th Computer Aided Verification (CAV’06). Lecture Notes in Computer Science, vol. 4144, pp. 372–385. Springer (2006)

Chander, A., Espinosa, D., Islam, N., Lee, P., Necula, G.: Enforcing resource bounds via static verification of dynamic checks. In: 14th European Symposium on Programming (ESOP’05). Lecture Notes in Computer Science, vol. 3444, pp. 311–325. Springer (2005)

Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: ACM Symposium on Principles of Programming Languages (POPL’77), pp. 238–252. ACM Press (1977)

Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: ACM Symposium on Principles of Programming Languages (POPL’78), pp. 84–97. ACM Press (1978)

Craig, S.-J., Leuschel, M.: Self-tuning resource aware specialisation for prolog. In: 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’05), pp. 23–34. ACM Press (2005)

Crary, K., Weirich, S.: Resource bound certification. In: 27th ACM Symposium on Principles of Programming Languages (POPL’05), pp. 184–198. ACM Press (2000)

Debray, S.K., Lin, N.W.: Cost Analysis of Logic Programs. ACM Trans. Program. Lang. Syst. 15(5), 826–875 (1993)

Floyd, R.W.: Assigning meanings to programs. In: Proceedings of Symposium in Applied Mathematics, vol. 19, Mathematical Aspects of Computer Science, pp. 19–32. American Mathematical Society, Providence, RI (1967)

Gómez, G., Liu, Y.A.: Automatic time-bound analysis for a higher-order language. In: Proceedings of the ACM SIGPLAN 2002 Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pp. 75–88. ACM Press (2002)

Hermenegildo, M., Puebla, G., Bueno, F., López-García, P.: Integrated program debugging, verification, and optimization using abstract interpretation (and The Ciao System Preprocessor). Sci. Comput. Program. 58(1–2), 115–140 (2005)

Hickey, T., Cohen, J.: Automating program analysis. J. ACM 35(1), 185–220 (1988)

Hofmann, M., Jost, S.: Static prediction of heap space usage for first-order functional programs. In: 30th Symposium on Principles of Programming Languages (POPL’03), pp. 185–197. ACM Press, New York (2003)

Jaffar, J., Maher, M.J.: Constraint logic programming: a survey. J. Log. Program. 19/20, 503–581 (1994)

Jones, N.D., Gomard, C.K., Sestoft, P.: Partial evaluation and automatic program generation. Prentice Hall, New York (1993)

Komorovski, J.: An introduction to partial deduction. In: Meta Programming in Logic (META’92). Lecture Notes in Computer Science, vol. 649, pp. 49–69. Springer, Heidelberg (1992)

Kristiansen, L., Jones, N.D.: The flow of data and the complexity of algorithms. In: 1st Conference on Computability in Europe (CiE’05). Lecture Notes in Computer Science, vol. 3526, pp. 263–274 (2005)

Le Metayer, D.: ACE: an automatic complexity evaluator. ACM Trans. Program. Lang. Syst. 10(2), 248–266 (1988)

Leuschel, M.: A framework for the integration of partial evaluation and abstract interpretation of logic programs. ACM Trans. Program. Lang. Syst. 26(3), 413–463 (2004)

Leuschel, M., Bruynooghe, M.: Logic program specialisation through partial deduction: control issues. Theory Pract. Log. Program. 2(4 & 5), 461–515 (2002)

Lloyd, J.W., Shepherdson, J.C.: Partial evaluation in logic programming. J. Log. Program. 11(3–4), 217–242 (1991)

Luca, B., Andrei, S., Anderson, H., Khoo, S.-C.: Program transformation by solving recurrences. In: ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation (PEPM ’06), pp. 121–129. ACM (2006)

Marion, J.-Y., Péchoux, R.: Sup-interpretations, a semantic method for static analysis of program resources. ACM Trans. Comput. Log. 10(4), 31 (2009) (Article 27)

Navas, J., Mera, E., López-García, P., Hermenegildo, M.: User-definable resource bounds analysis for logic programs. In: 23rd International Conference on Logic Programming (ICLP’07), vol. 4670 of LNCS, pp. 348–363. Springer, Heidelberg (2007)

Necula, G.: Proof-carrying code. In: ACM Symposium on Principles of Programming Languages (POPL 1997), pp. 106–119. ACM Press, New York (1997)

Niggl, K.-H., Wunderlich, H.: Certifying polynomial time and linear/polynomial space for imperative programs. SIAM J. Comput. 35(5), 1122–1147 (2006)

Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: 5th International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI’04). Lecture Notes in Computer Science, pp. 239–251. Springer, Heidelberg (2004)

Puebla, G., Ochoa, C.: Poly-controlled partial evaluation. In: 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP’06), pp. 261–271. ACM Press, New York (2006)

Rosendahl, M.: Automatic complexity analysis. In: 4th ACM Conference on Functional Programming Languages and Computer Architecture (FPCA’89), pp. 144–156. ACM Press (1989)

Rosendahl, M.: Simple driving techniques. In: Mogensen, T., Schmidt, D., Hal Sudborough, I. (eds.) The Essence of Computation. Lecture Notes in Computer Science, vol. 2566, pp. 404–419. Springer, Heidelberg (2002)

Sands, D.: A naïve time analysis and its theory of cost equivalence. J. Log. Comput. 5(4), 495–541 (1995)

Shamir, A.: A linear time algorithm for finding minimum cutsets in reducible graphs. SIAM J. Comput. 8(4), 645–655 (1979)

Spoto, F., Hill, P.M., Payet, E.: Path-length analysis of object-oriented programs. In: 1st International Workshop on Emerging Applications of Abstract Interpretation (EAAI’06), Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam (2006)

Turchin, V.F.: The concept of a supercompiler. ACM Trans. Program. Lang. Syst. 8(3), 292–325 (1986)

Wadler, P.: Strictness analysis aids time analysis. In: ACM Symposium on Principles of Programming Languages (POPL’88), pp. 119–132. ACM Press (1988)

Wegbreit, B.: Mechanical program analysis. Commun. ACM 18(9), 69–73 (1975)