A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems

DOI10.1007/978-3-642-22438-6_32zbMath1314.68173OpenAlexW38697619MaRDI QIDQ5200041

Fabian Emmes, Lars Noschinski, Jürgen Giesl

Publication date: 29 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22438-6_32

Mathematics Subject Classification ID

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

Related Items (3)

A combination framework for complexity ⋮ Analyzing Innermost Runtime Complexity Through Tuple Interpretations ⋮ Analyzing innermost runtime complexity of term rewriting by dependency pairs

Uses Software

• Haskell

Cites Work

• Unnamed Item
• On tree automata that certify termination of left-linear term rewriting systems
• Mechanizing and improving dependency pairs
• Matrix interpretations for proving termination of term rewriting
• Termination of term rewriting using dependency pairs
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Automating the dependency pair method
• Algorithms with polynomial interpretation termination proof
• Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
• Automated Implicit Computational Complexity Analysis (System Description)
• Automated Complexity Analysis Based on the Dependency Pair Method
• Complexity Analysis by Graph Rewriting
• Automated termination analysis for logic programs with cut
• Dependency Pairs and Polynomial Path Orders
• Term Rewriting and All That
• Revisiting Matrix Interpretations for Polynomial Derivational Complexity of Term Rewriting
• Closing the Gap Between Runtime Complexity and Polytime Computability.
• Automated Termination Analysis of Java Bytecode by Term Rewriting
• POLYNOMIALLY BOUNDED MATRIX INTERPRETATIONS
• Modular Complexity Analysis via Relative Complexity
• Complexity, Graphs, and the Dependency Pair Method
• Logic for Programming, Artificial Intelligence, and Reasoning
• Polynomial-time computation via local inference relations

This page was built for publication: A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems