Automated Implicit Computational Complexity Analysis (System Description)

DOI10.1007/978-3-540-71070-7_10MaRDI QIDQ3541694zbMATH OpenOpenAlexFDO

Authors Martin Avanzini, Georg Moser, Andreas Schnabl

Publication date 27 November 2008

Published in Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-71070-7_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• Complexity analysis by graph rewriting
• Automated higher-order complexity analysis
• Polynomial path orders
• Automated Complexity Analysis Based on Context-Sensitive Rewriting
• Analysing the implicit complexity of programs.

Cites work

• Algorithms with polynomial interpretation termination proof
• Analysing the implicit complexity of programs.
• Complexity Analysis by Rewriting
• Generating polynomial orderings
• scientific article; zbMATH DE number 1696756 (Why is no real title available?)
• scientific article; zbMATH DE number 794240 (Why is no real title available?)
• Maximal Termination
• Mechanically proving termination using polynomial interpretations
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• Proving Termination Using Recursive Path Orders and SAT Solving
• Quasi-interpretation Synthesis by Decomposition
• Resource Analysis by Sup-interpretation
• SAT Solving for Termination Analysis with Polynomial Interpretations
• Term Rewriting and Applications
• Termination of term rewriting using dependency pairs
• Termination proofs and the length of derivations

Cited in

(6)

• Automated higher-order complexity analysis
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Automated complexity analysis based on ordered resolution
• Dependency Pairs and Polynomial Path Orders
• scientific article; zbMATH DE number 2087550 (Why is no real title available?)
• A dependency pair framework for innermost complexity analysis of term rewrite systems

This page was built for publication: Automated Implicit Computational Complexity Analysis (System Description)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541694)