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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
|
|
Download this file (PDF/344kB) |
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 |
|
|
|
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: | 05 Nov 2024 11:02 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/64982 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):