HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Implementation and Complexity of the Lowest Static Reduction

Ludovic Henrio 1 Bernard Paul Serpette Szabolcs Szentes
1 OASIS - Active objects, semantics, Internet and security
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The lowest static reduction (LSR) is the 0^th-order Control-Flow Analysis without continuation passing style (CPS) consideration. This article presents some algorithms resolving LSR and their related complexities. Even if this analysis is generally declared to be computable in cubic time, a stand alone algorithm reaching this complexity is not so straightforward. With the -calculus as input language, we will start with a blind algorithm and step by step we will finally exhibit the algorithm which run, for worst cases, in cubic time related to the size of the program.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:55:26 PM
Last modification on : Friday, February 4, 2022 - 3:08:49 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:24:34 PM


  • HAL Id : inria-00071550, version 1



Ludovic Henrio, Bernard Paul Serpette, Szabolcs Szentes. Implementation and Complexity of the Lowest Static Reduction. RR-5034, INRIA. 2003. ⟨inria-00071550⟩



Record views


Files downloads