Termination of Innermost-Terminating Right-Linear Overlay Term Rewrite Systems
arXiv:2604.20754
Abstract
It has been shown that, regarding a terminating right-linear overlay term rewrite system (TRS), any rewrite sequence terminating in a normal form can be simulated by an innermost reduction. In this paper, using this simulation property, we show that for a right-linear overlay TRS, there is no infinite minimal dependency-pair chain if and only if there is no infinite innermost minimal dependency-pair chain. As a consequence, termination and innermost termination coincide for the class of right-linear overlay TRSs.
Presented at WST 2026