Resource control of object-oriented programs

Conference object, Preprint English OPEN
Marion , Jean-Yves ; Péchoux , Romain (2007)
  • Publisher: HAL CCSD
  • Subject: Computer Science - Programming Languages | [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC] | Computer Science - Logic in Computer Science | F.2 | ACM : F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

International audience; A sup-interpretation is a tool which provides an upper bound on the size of a value computed by some symbol of a program. Sup-interpretations have shown their interest to deal with the complexity of first order functional programs. For instance, they allow to characterize all the functions bitwise computable in \texttt{Alogtime}. This paper is an attempt to adapt the framework of sup-interpretations to a fragment of oriented-object programs, including distinct encodings of numbers through the use of constructor symbols, loop and while constructs and non recursive methods with side effects. We give a criterion, called brotherly criterion, which ensures that each brotherly program computes objects whose size is polynomially bounded by the inputs sizes.
  • References (14)
    14 references, page 1 of 2

    [1] R. Amadio, S. Coupet-Grimal, S. Dal-Zilio, and L. Jakubiec. A functional scenario for bytecode veri cation of resource bounds. In CSL, volume 3210 of LNCS, pages 265{279. Springer, 2004.

    [2] R. Amadio and S. Dal-Zilio. Resource control for synchronous cooperative threads. In Concur, pages 68{82, 2004.

    [3] T. Arts and J. Giesl. Termination of term rewriting using dependency pairs. Theoretical Computer Science, 236:133{178, 2000.

    [4] M. Blum. A machine-independent theory of the complexity of recursive functions. Journal of the Association for Computing Machinery, 14:322{336, 1967.

    [5] G. Bonfante, J.-Y. Marion, and J.-Y. Moyen. Quasi-interpretation a way to control resources. Submitted to Theoretical Computer Science, 2005.

    [6] G. Bonfante, J.-Y. Marion, and R. Pechoux. A characterization of alternating log time by rst order functional programs. In LPAR 2006, volume 4246 of LNAI, pages 90{104, 2006.

    [7] S. Dal-Zilio and R. Gascon. Resource bound certi cation for a tail-recursive virtual machine. In APLAS 2005, volume 3780 of LNCS, pages 247{263. Springer-Verlag, 2005.

    [8] S. Drossopoulou and S. Eisenbach. Describing the semantics of Java and proving type soundness. Formal Syntax and Semantics of Java, pages 41{82, 1999.

    [9] A. Igarashi, B.C. Pierce, and P. Wadler. Featherweight Java: A Minimal Core Calculus for Java and GJ. ACM Transactions on Programming Languages and Systems, 23(3):396{450, 2001.

    [10] L. Kristiansen and N.D. Jones. The ow of data and the complexity of algorithms. New Computational Paradigms, 3526:263{274.

  • Similar Research Results (6)
  • Metrics
    No metrics available
Share - Bookmark