3 papers
cs.LO2025
Dependency Pairs for Expected Innermost Runtime Complexity and Strong Almost-Sure Termination of Probabilistic Term Rewriting
Jan-Christoph Kassing, Leon Spitzer, Jürgen Giesl
The dependency pair (DP) framework is one of the most powerful techniques for automatic termination and complexity analysis of term rewrite systems. While DPs were extended to prov…
cs.LO2025
Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems
Emma Ahrens, Jan-Christoph Kassing, Jürgen Giesl +1
We present novel semiring semantics for abstract reduction systems (ARSs). More precisely, we provide a weighted version of ARSs, where the reduction steps induce weights from a se…
cs.LO2024
The Annotated Dependency Pair Framework for Almost-Sure Termination of Probabilistic Term Rewriting
Jan-Christoph Kassing, Jürgen Giesl
Dependency pairs are one of the most powerful techniques to analyze termination of term rewrite systems automatically. We adapt dependency pairs to the probabilistic setting and de…