Automated Implicit Computational Complexity Analysis (System Description)

DOI10.1007/978-3-540-71070-7_10zbMath1165.68444OpenAlexW86123047MaRDI QIDQ3541694

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)

Related Items

A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems, Dependency Pairs and Polynomial Path Orders, Analyzing innermost runtime complexity of term rewriting by dependency pairs

Cites Work

• Unnamed Item
• Unnamed Item
• Mechanically proving termination using polynomial interpretations
• Generating polynomial orderings
• Analysing the implicit complexity of programs.
• Termination of term rewriting using dependency pairs
• Algorithms with polynomial interpretation termination proof
• Resource Analysis by Sup-interpretation
• Maximal Termination
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• Proving Termination Using Recursive Path Orders and SAT Solving
• Quasi-interpretation Synthesis by Decomposition
• SAT Solving for Termination Analysis with Polynomial Interpretations
• Termination proofs and the length of derivations
• Complexity Analysis by Rewriting
• Term Rewriting and Applications