Algorithms with polynomial interpretation termination proof
From MaRDI portal
Publication:2740985
DOI10.1017/S0956796800003877zbMath0987.68042OpenAlexW2055717180MaRDI QIDQ2740985
Guillaume Bonfante, Hélène Touzet, Adam Cichon, Jean-Yves Marion
Publication date: 9 September 2001
Published in: Journal of Functional Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0956796800003877
Related Items (23)
A combination framework for complexity ⋮ Higher-order interpretations and program complexity ⋮ Unnamed Item ⋮ A Short Introduction to Implicit Computational Complexity ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Mechanically proving termination using polynomial interpretations ⋮ Analyzing Innermost Runtime Complexity Through Tuple Interpretations ⋮ Proving Quadratic Derivational Complexities Using Context Dependent Interpretations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Automated Implicit Computational Complexity Analysis (System Description) ⋮ Automated Complexity Analysis Based on the Dependency Pair Method ⋮ Quasi-interpretations. A way to control resources ⋮ On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting ⋮ A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems ⋮ Complexity Analysis by Rewriting ⋮ Applications and extensions of context-sensitive rewriting ⋮ Derivational complexity and context-sensitive Rewriting ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Real or natural number interpretation and their effect on complexity ⋮ Characterizing polynomial time complexity of stream programs using interpretations ⋮ Intensional Properties of Polygraphs ⋮ Analyzing innermost runtime complexity of term rewriting by dependency pairs
This page was built for publication: Algorithms with polynomial interpretation termination proof
