Comparing on Strings : Iterated Syllable Ordering & Recursive Path Ordering

Abstract

The recursive path ordering introduced by Dershowitz can prove the termination of term rewriting systems. On string rewriting systems, the iterated syllable (or collecting) ordering is a total ordering. We will prove that the recursive path ordering on monadic terms is equivalent to the iterated syllable ordering on the reverse words.