Dependency Pairs and Polynomial Path Orders

DOI10.1007/978-3-642-02348-4_4zbMath1242.68126arXiv0904.0981OpenAlexW1549644090MaRDI QIDQ3636818

Martin Avanzini, Georg Moser

Publication date: 30 June 2009

Published in: Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.0981

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, Analyzing innermost runtime complexity of term rewriting by dependency pairs

Uses Software

• MiniSat

Cites Work

• Quasi-interpretations. A way to control resources
• Matrix interpretations for proving termination of term rewriting
• The realm of primitive recursion
• A new recursion-theoretic characterization of the polytime functions
• Analysing the implicit complexity of programs.
• Termination of term rewriting using dependency pairs
• Polynomial Path Orders
• Automated Implicit Computational Complexity Analysis (System Description)
• Automated Complexity Analysis Based on the Dependency Pair Method
• SAT Solving for Termination Analysis with Polynomial Interpretations
• Term Rewriting and All That
• Theory and Applications of Satisfiability Testing
• Complexity Analysis by Rewriting
• Frontiers of Combining Systems
• Uncurrying for Termination
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science