A Complexity Preserving Transformation from Jinja Bytecode to Rewrite Systems

Michael Schaper

Presented at the 5th Workshop on Developments in Implicit Computational Complexity (DICE 2014), 2014.


We revisit known transformations from object-oriented bytecode programs to rewrite systems from the viewpoint of runtime complexity. Suitably generalising the constructions proposed in the literature, we define an alternative representation of Jinja bytecode (JBC) executions as computation graphs from which we obtain a representation of JBC executions as constrained rewrite systems. We show that the transformation is complexity preserving. We restrict to non-recursive methods and make use of a heap shape pre-analysis.




author = "Michael Schaper",
title = "A Complexity Preserving Transformation from {Jinja} Bytecode to Rewrite Systems",
note = "Presented at {DICE} 2014",
year = 2014
Nach oben scrollen