Skip to Main content Skip to Navigation
Journal articles

Characterizing polynomial time complexity of stream programs using interpretations

Hugo Férée 1 Emmanuel Hainry 1 Mathieu Hoyrup 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : This paper provides a criterion based on interpretation methods on term rewrite systems in order to characterize the polynomial time complexity of second order functionals. For that purpose it introduces a first order functional stream language that allows the programmer to implement second order functionals. This characterization is extended through the use of exp-poly interpretations as an attempt to capture the class of Basic Feasible Functionals (bff). Moreover, these results are adapted to provide a new characterization of polynomial time complexity in computable analysis. These characterizations give a new insight on the relations between the complexity of functional stream programs and the classes of functions computed by Oracle Turing Machine, where oracles are treated as inputs.
Document type :
Journal articles
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Monday, February 2, 2015 - 1:09:22 PM
Last modification on : Tuesday, December 7, 2021 - 9:10:01 AM
Long-term archiving on: : Wednesday, May 27, 2015 - 3:40:53 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux. Characterizing polynomial time complexity of stream programs using interpretations. Theoretical Computer Science, Elsevier, 2015, 585, pp.41-54. ⟨10.1016/j.tcs.2015.03.008⟩. ⟨hal-01112160⟩



Les métriques sont temporairement indisponibles