Jürgen Giesl

From Innermost to Full Probabilistic Term Rewriting: Almost-Sure Termination, Complexity, and Modularity

2024 · arXiv (Cornell University)

There are many evaluation strategies for term rewrite systems, but automatically proving termination or analyzing complexity is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies (full) termination or when runtime …