Skip to Main content Skip to Navigation
Conference papers

Interpretation of stream programs: characterizing type 2 polynomial time complexity

Abstract : We study polynomial time complexity of type 2 functionals. For that purpose, we introduce a first order functional stream language. We give criteria, named well-founded, on such programs relying on second order interpretation that characterize two variants of type 2 polynomial complexity including the Basic Feasible Functions (BFF). These charac- terizations provide a new insight on the complexity of stream programs. Finally, we adapt these results to functions over the reals, a particular case of type 2 functions, and we provide a characterization of polynomial time complexity in Recursive Analysis.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Friday, September 17, 2010 - 10:50:48 AM
Last modification on : Tuesday, December 7, 2021 - 9:10:02 AM
Long-term archiving on: : Saturday, December 18, 2010 - 2:59:04 AM


Files produced by the author(s)


  • HAL Id : inria-00518381, version 1



Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux. Interpretation of stream programs: characterizing type 2 polynomial time complexity. 21st International Symposium on Algorithms and Computation - ISAAC 2010, Dec 2010, Jeju Island, South Korea. ⟨inria-00518381⟩



Les métriques sont temporairement indisponibles