From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
Open Access
- 6 April 2024
- book chapter
- Published by Springer Nature
- p. 206-228
Abstract
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems. These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool .Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Automated Expected Amortised Cost Analysis of Probabilistic Data Structures2022
- Automated Termination Analysis of Polynomial Probabilistic Programs2021
- Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes2021
- mu-term: Verify Termination Properties Automatically (System Description)2020
- Computing Expected Runtimes for Constant Probability Programs2019
- Transforming Derivational Complexity of Term Rewriting to Runtime ComplexityLecture Notes in Computer Science, 2019
- Termination of Nondeterministic Probabilistic Programs2019
- Probabilistic Rewrite Strategies. Applications to ELAN2002
- Probabilistic LCF1978
- Computing in systems described by equationsLecture Notes in Computer Science, 1977