Skip to main content

Characterizing polynomial time complexity of stream programs using interpretations

Férée, Hugo, Hainry, Emmanuel, Hoyrup, Mathieu, Péchoux, Romain (2015) Characterizing polynomial time complexity of stream programs using interpretations. Theoretical Computer Science, 585 . pp. 41-54. ISSN 0304-3975. (doi:10.1016/j.tcs.2015.03.008)

PDF - Author's Accepted Manuscript

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Download (317kB) Preview
PDF - Author's Accepted Manuscript
Restricted to Repository staff only
Contact us about this Publication Download (302kB)
Official URL


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.

Item Type: Article
DOI/Identification number: 10.1016/j.tcs.2015.03.008
Uncontrolled keywords: Stream Programs, Type-2 Functionals, Interpretations, Polynomial Time, Basic Feasible Functionals, Computable Analysis, Rewriting
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Hugo Feree
Date Deposited: 05 Dec 2017 13:04 UTC
Last Modified: 29 May 2019 19:58 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year