Complexity Analysis by Rewriting
From MaRDI portal
Publication:5458433
Recommendations
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)