Back to Search
Start Over
Annotated Dependency Pairs for Full Almost-Sure Termination of Probabilistic Term Rewriting
- Publication Year :
- 2024
-
Abstract
- Dependency pairs (DPs) are one of the most powerful techniques for automated termination analysis of term rewrite systems. Recently, we adapted the DP framework to the probabilistic setting to prove almost-sure termination (AST) via annotated DPs (ADPs). However, this adaption only handled AST w.r.t. the innermost evaluation strategy. In this paper, we improve the ADP framework to prove AST for full rewriting. Moreover, we refine the framework for rewrite sequences that start with basic terms containing a single defined function symbol. We implemented and evaluated the new framework in our tool AProVE.<br />Comment: arXiv admin note: text overlap with arXiv:2305.11741
- Subjects :
- Computer Science - Logic in Computer Science
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2408.06768
- Document Type :
- Working Paper