Characterizing polynomial time complexity of stream programs using interpretations

DOI10.1016/j.tcs.2015.03.008zbMath1327.68075OpenAlexW2036258793MaRDI QIDQ2346991

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

Publication date: 26 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.008

zbMATH Keywords

interpretationsrewritingpolynomial timecomputable analysisbasic feasible functionalstype-2 functionalsstream programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Functional programming and lambda calculus (68N18) Grammars and rewriting systems (68Q42)

Related Items

Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Unnamed Item ⋮ Polynomial time over the reals with parsimony ⋮ Unnamed Item

Cites Work

• Quasi-interpretations. A way to control resources
• Productivity of stream definitions
• A new recursion-theoretic characterization of the polytime functions
• Synthesis of sup-interpretations: a survey
• Algorithms with polynomial interpretation termination proof
• On characterizations of the basic feasible functionals, Part I
• Sup-interpretations, a semantic method for static analysis of program resources
• Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity
• Upper Bounds on Stream I/O Using Semantic Interpretations
• Higher-Order Interpretations and Program Complexity
• A new Characterization of Type-2 Feasibility
• Feasible Functions over Co-inductive Data
• Ramified Corecurrence and Logspace
• Derivational Complexity Is an Invariant Cost Model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item