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.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 585, pp.41-54. 〈10.1016/j.tcs.2015.03.008〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01112160
Contributeur : Romain Péchoux <>
Soumis le : lundi 2 février 2015 - 13:09:22
Dernière modification le : jeudi 22 septembre 2016 - 14:31:34
Document(s) archivé(s) le : mercredi 27 mai 2015 - 15:40:53

Fichier

FEREE_HAINRY_HOYRUP_PECHOUX.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

547

Téléchargements de fichiers

139