Complexity Analysis by Rewriting

DOI10.1007/978-3-540-78969-7_11zbMath1137.68417OpenAlexW4235201325MaRDI QIDQ5458433

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

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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