3526 articles – 5249 references  [version française]

hal-00067838, version 1

Heap-size analysis for assembly programs

Jean-Yves Marion () 1, Jean-Yves Moyen () 2

(2006)

Abstract: Our objective is to propose methods for resource-aware compilation inspired by the implicit complexity community. We consider a small assembly-like language and we build abstract finite machine models in order to predict a bound on the maximal heap usage of a program. We propose a polynomial time procedure to detect and certify a broad and meaningful class of non-size increasing programs, which run in a constant size heap. We end by discussing about programs running in linear heap space and discussing how to capture logarithmic space computation.

  • 1:  CALLIGRAMME (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2:  Laboratoire d'informatique de Paris-nord (LIPN)
  • CNRS : UMR7030 – Université Paris XIII - Paris Nord
  • Collaboration : ACI Criss
  • Domain : Computer Science/Logic in Computer Science
  • Keywords : Non-Size increasing – program analysis
 
  • hal-00067838, version 1
  • http://hal.archives-ouvertes.fr/hal-00067838
  • oai:hal.archives-ouvertes.fr:hal-00067838
  • From: Jean-Yves Moyen <>
  • Submitted on: Tuesday, 9 May 2006 14:05:46
  • Updated on: Tuesday, 9 May 2006 14:08:01