Complexity Analysis by Rewriting
From MaRDI portal
Publication:5458433
DOI10.1007/978-3-540-78969-7_11zbMath1137.68417OpenAlexW4235201325MaRDI QIDQ5458433
Publication date: 11 April 2008
Published in: Functional and Logic Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-78969-7_11
Related Items (10)
Unnamed Item ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Analyzing Innermost Runtime Complexity Through Tuple Interpretations ⋮ Proving Quadratic Derivational Complexities Using Context Dependent Interpretations ⋮ Automated Implicit Computational Complexity Analysis (System Description) ⋮ Automated Complexity Analysis Based on the Dependency Pair Method ⋮ A Formalization of Polytime Functions ⋮ Dependency Pairs and Polynomial Path Orders ⋮ 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
- Mechanically proving termination using polynomial interpretations
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
- A new recursion-theoretic characterization of the polytime functions
- A term rewriting characterization of the polytime functions and related complexity classes
- Analysing the implicit complexity of programs.
- Proof-theoretic analysis of termination proofs
- An arithmetic for polynomial-time computation
- Algorithms with polynomial interpretation termination proof
- Proving Termination Using Recursive Path Orders and SAT Solving
- Termination proofs and the length of derivations
- Derivational Complexity of Knuth-Bendix Orders Revisited
- Satisfying KBO Constraints
- Term Rewriting and Applications
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Rewriting Techniques and Applications
- Derivation lengths and order types of Knuth--Bendix orders
This page was built for publication: Complexity Analysis by Rewriting
