A Dependency Pair Framework for Relative Termination of Term Rewriting
Open Access
- 2 July 2024
- book chapter
- Published by Springer Nature
- p. 360-380
Abstract
Dependency pairs are one of the most powerful techniques for proving termination of term rewrite systems (TRSs), and they are used in almost all tools for termination analysis of TRSs. Problem #106 of the RTA List of Open Problems asks for an adaption of dependency pairs for relative termination. Here, infinite rewrite sequences are allowed, but one wants to prove that a certain subset of the rewrite rules cannot be used infinitely often. Dependency pairs were recently adapted to annotated dependency pairs (ADPs) to prove almost-sure termination of probabilistic TRSs. In this paper, we develop a novel adaption of ADPs for relative termination. We implemented our new ADP framework in our tool and evaluate it in comparison to state-of-the-art tools for relative termination of TRSs.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Proving Almost-Sure Innermost Termination of Probabilistic Term Rewriting Using Dependency Pairs2023
- Analysing Parallel Complexity of Term Rewriting2022
- mu-term: Verify Termination Properties Automatically (System Description)2020
- Transforming Derivational Complexity of Term Rewriting to Runtime ComplexityLecture Notes in Computer Science, 2019
- The Termination and Complexity Competition2019
- Complexity Analysis for Term Rewriting by Integer Transition Systems2017
- Nagoya Termination Tool2014
- Proving Liveness with Fairness Using RewritingLecture Notes in Computer Science, 2005
- Matchbox: A Tool for Match-Bounded String RewritingLecture Notes in Computer Science, 2004
- Dependency Pairs for Equational RewritingLecture Notes in Computer Science, 2001