Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity

DOI10.1007/978-3-642-17517-6_27zbMATH Open1311.03068OpenAlexW1540704421MaRDI QIDQ3060741FDOQ3060741

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

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)

Cited In (4)

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

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)