Skip to main content
Kent Academic Repository

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) (KAR id:64982)

PDF Author's Accepted Manuscript
Language: English


Download this file
(PDF/344kB)
[thumbnail of polynomial_stream.pdf]
Preview
Request a format suitable for use with assistive technology e.g. a screenreader
PDF Author's Accepted Manuscript
Language: English

Restricted to Repository staff only
[thumbnail of polynomial_stream.pdf]
Official URL:
https://doi.org/10.1016/j.tcs.2015.03.008

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.

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: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Hugo Feree
Date Deposited: 05 Dec 2017 13:04 UTC
Last Modified: 04 Jul 2023 13:36 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/64982 (The current URI for this page, for reference purposes)

University of Kent Author Information

Férée, Hugo.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.