Analyzing Innermost Runtime Complexity Through Tuple Interpretations

DOI10.4204/EPTCS.376.5arXiv2303.13256OpenAlexW4353057097MaRDI QIDQ6118746

Deivid Vale, Unnamed Author

Publication date: 28 February 2024

Published in: Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Semantics in the theory of computing (68Q55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Higher-order interpretations and program complexity
• Termination of rewriting systems by polynomial interpretations and its implementation
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• Mechanically proving termination using polynomial interpretations
• Counterexamples to termination for the direct sum of term rewriting systems
• Analyzing program termination and complexity automatically with \textsf{AProVE}
• Algorithms with polynomial interpretation termination proof
• SAT-based termination analysis using monotonicity constraints over the integers
• Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
• Automated Complexity Analysis Based on the Dependency Pair Method
• Termination proofs and the length of derivations
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems
• Complexity Analysis by Rewriting
• Tuple Interpretations for Higher-Order Complexity.

This page was built for publication: Analyzing Innermost Runtime Complexity Through Tuple Interpretations