Interpretation of stream programs: characterizing type 2 polynomial time complexity

DOI10.1007/978-3-642-17517-6_27MaRDI QIDQ3060741zbMATHOpenAlexFDO

Authors Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17517-6_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) Complexity of computation (including implicit computational complexity) (03D15) Higher-type and set recursion theory (03D65)

Recommendations

• Characterizing polynomial time complexity of stream programs using interpretations
• Higher-order interpretations and program complexity
• Higher order interpretation for higher order complexity
• Higher-order interpretations and program complexity
• On characterizations of the basic feasible functionals. I

Cited in

(5)

• On the complexity of stream equality
• Characterizing polynomial time complexity of stream programs using interpretations
• Translation of tree-processing programs into stream-processing programs based on ordered linear type
• Global and local space properties of stream programs
• Ramified Corecurrence and Logspace

This page was built for publication: Interpretation of stream programs: characterizing type 2 polynomial time complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060741)