Termination of String Rewriting Rules That Have One Pair of Overlaps

This paper presents a partial solution to the long standing open problem of termination of one-rule string rewriting. Overlaps between the two sides of the rule play a central role in existing termination criteria. Wecharacterize termination of all one-rule string rewriting systems that have one suchoverlap at either end. This both completes a result of Kurth and generalizes a result of Shikishima-Tsuji et al