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
Liste complète des métadonnées

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01112160
Contributor : Romain Péchoux <>
Submitted on : Monday, February 2, 2015 - 1:09:22 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Document(s) archivé(s) le : Wednesday, May 27, 2015 - 3:40:53 PM

File

FEREE_HAINRY_HOYRUP_PECHOUX.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

655

Files downloads

176