Complexity Analysis by Rewriting
From MaRDI portal
Publication:5458433
DOI10.1007/978-3-540-78969-7_11zbMATH Open1137.68417OpenAlexW4235201325MaRDI QIDQ5458433FDOQ5458433
Authors: Martin Avanzini, Georg Moser 
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
Recommendations
Cites Work
- A new recursion-theoretic characterization of the polytime functions
- Algorithms with polynomial interpretation termination proof
- Termination proofs and the length of derivations
- Proof-theoretic analysis of termination proofs
- Title not available (Why is that?)
- Rewriting Techniques and Applications
- Proving Termination Using Recursive Path Orders and SAT Solving
- Mechanically proving termination using polynomial interpretations
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
- Derivation lengths and order types of Knuth--Bendix orders
- Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
- Analysing the implicit complexity of programs.
- Title not available (Why is that?)
- An arithmetic for polynomial-time computation
- Derivational Complexity of Knuth-Bendix Orders Revisited
- Satisfying KBO Constraints
- Title not available (Why is that?)
- A term rewriting characterization of the polytime functions and related complexity classes
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Term Rewriting and Applications
Cited In (16)
- Automated Complexity Analysis Based on Context-Sensitive Rewriting
- Reverse complexity
- Title not available (Why is that?)
- Analysing the implicit complexity of programs.
- Complexity analysis of term-rewriting systems
- Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
- Automated Implicit Computational Complexity Analysis (System Description)
- Dependency Pairs and Polynomial Path Orders
- A new order-theoretic characterisation of the polytime computable functions
- On quasi-interpretations, blind abstractions and implicit complexity
- A Formalization of Polytime Functions
- Automated Complexity Analysis Based on the Dependency Pair Method
- Automated complexity analysis based on ordered resolution
- Title not available (Why is that?)
- Analyzing Innermost Runtime Complexity Through Tuple Interpretations
- Real or natural number interpretation and their effect on complexity
This page was built for publication: Complexity Analysis by Rewriting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458433)
