Efficient first order functional program interpreter with time bound certifications

Jean-Yves Marion; Jean-Yves Moyen

Efficient first order functional program interpreter with time bound certifications

Jean-Yves Marion ¹ Jean-Yves Moyen ¹

1 CALLIGRAMME - Linear logic, proof networks and categorial grammars

INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Abstract : We demonstrate that the class of functions computed by first order functional programs over lists which terminate by multiset path ordering and admit a polynomial quasi-interpretation, is exactly the class of function computable in polynomial time. The interest of this result lies on (i) the simplicity of the conditions on programs to certify their complexity, (ii) the fact that an important class of natural programs is captured, (iii) potential applications for program optimization.

Mots-clés : analyse complexité program transformation runtime analysis transformation programmes

Document type :

Conference papers

Domain :

Computer Science [cs] / Other [cs.OH]

Complete list of metadatas

https://hal.inria.fr/inria-00099178
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:51:33 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM

Efficient first order functional program interpreter with time bound certifications

Identifiers

Collections

Citation

Export

Metrics

90

Contact

Efficient first order functional program interpreter with time bound certifications

Identifiers

Collections

Citation

Export

Share

Metrics

90

Contact