Characterizing polynomial time complexity of stream programs using interpretations

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.

Authors

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

Keywords

• Stream programs
• Type-2 functionals
• Interpretations
• Polynomial time
• Basic feasible functionals
• Computable analysis
• Rewriting