Analysing the implicit complexity of programs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2003

Analysing the implicit complexity of programs

Résumé

We study termination proofs in order to (i) determine computational complexity of programs and (ii) generate efficient programs from the complexity analysis. For this, we construct a termination ordering, called light multiset path ordering (LMPO), which is a restriction of the multiset path ordering. We establish that the class of first order functional programs on lists which is terminating by LMPO characterises exactly the functions computable in polynomial time.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

inria-00099505 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00099505 , version 1

Citer

Jean-Yves Marion. Analysing the implicit complexity of programs. Information and Computation, 2003, 183, pp.2-18. ⟨inria-00099505⟩
59 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More