Complexity Analysis by Rewriting

DOI10.1007/978-3-540-78969-7_11MaRDI QIDQ5458433zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Polynomial path orders
• Dependency Pairs and Polynomial Path Orders
• Automated Complexity Analysis Based on Context-Sensitive Rewriting
• Complexity analysis by graph rewriting
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

Cites work

• scientific article; zbMATH DE number 2043537 (Why is no real title available?)
• scientific article; zbMATH DE number 1889386 (Why is no real title available?)
• scientific article; zbMATH DE number 794240 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• A term rewriting characterization of the polytime functions and related complexity classes
• Algorithms with polynomial interpretation termination proof
• An arithmetic for polynomial-time computation
• Analysing the implicit complexity of programs.
• Derivation lengths and order types of Knuth--Bendix orders
• Derivational Complexity of Knuth-Bendix Orders Revisited
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Mechanically proving termination using polynomial interpretations
• Proof-theoretic analysis of termination proofs
• Proving Termination Using Recursive Path Orders and SAT Solving
• Rewriting Techniques and Applications
• Satisfying KBO Constraints
• Term Rewriting and Applications
• Termination proofs and the length of derivations
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths

Cited in

(18)

• Analysing the implicit complexity of programs.
• Complexity of conditional term rewriting
• Reverse complexity
• Polynomial path orders
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• On quasi-interpretations, blind abstractions and implicit complexity
• Dependency Pairs and Polynomial Path Orders
• scientific article; zbMATH DE number 4001501 (Why is no real title available?)
• A new order-theoretic characterisation of the polytime computable functions
• Automated complexity analysis based on ordered resolution
• A formalization of polytime functions
• Complexity analysis of term-rewriting systems
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Automated Complexity Analysis Based on Context-Sensitive Rewriting
• Automated Implicit Computational Complexity Analysis (System Description)
• Analyzing Innermost Runtime Complexity Through Tuple Interpretations
• Automated Complexity Analysis Based on the Dependency Pair Method
• 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)