Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
From MaRDI portal
Publication:3522024
DOI10.1007/978-3-540-70590-1_19zbMath1145.68452OpenAlexW1588175212MaRDI QIDQ3522024
Publication date: 28 August 2008
Published in: Rewriting Techniques and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70590-1_19
Related Items
Automated Implicit Computational Complexity Analysis (System Description), A new order-theoretic characterisation of the polytime computable functions, Real or natural number interpretation and their effect on complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
- Deleting string rewriting systems preserve regularity
- Mechanically proving termination using polynomial interpretations
- On tree automata that certify termination of left-linear term rewriting systems
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
- Analysing the implicit complexity of programs.
- Algorithms with polynomial interpretation termination proof
- Resource Analysis by Sup-interpretation
- Automated Complexity Analysis Based on the Dependency Pair Method
- SAT Solving for Termination Analysis with Polynomial Interpretations
- Termination proofs and the length of derivations
- Derivational Complexity of Knuth-Bendix Orders Revisited
- Proving Termination of Rewrite Systems Using Bounds
- Complexity Analysis by Rewriting
- Term Rewriting and Applications
