The Derivational Complexity Induced by the Dependency Pair Method

DOI10.1007/978-3-642-02348-4_18zbMath1242.68138arXiv0904.0570OpenAlexW2113881596MaRDI QIDQ5902127

Georg Moser, Andreas Schnabl

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.0570

Mathematics Subject Classification ID

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

Related Items

A combination framework for complexity, Uncurrying for termination and complexity

Uses Software

• Tyrolean

Cites Work

• Unnamed Item
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• Tyrolean termination tool: techniques and features
• Matrix interpretations for proving termination of term rewriting
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Termination of term rewriting using dependency pairs
• Automating the dependency pair method
• Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
• Arctic Termination ...Below Zero
• Automated Complexity Analysis Based on the Dependency Pair Method
• Term Rewriting and All That
• Derivational Complexity of Knuth-Bendix Orders Revisited
• Complexity, Graphs, and the Dependency Pair Method
• The Derivational Complexity Induced by the Dependency Pair Method
• Derivation lengths and order types of Knuth--Bendix orders