We propose a notion of complexity for oriented conditional term rewrite#N#systems satisfying certain restrictions. This notion is realistic in the sense#N#that it measures not only successful computations, but also partial#N#computations that result in a failed rule application. A transformation to#N#unconditional context-sensitive rewrite systems is presented which reflects#N#this complexity notion, as well as a technique to derive runtime and#N#derivational complexity bounds for the result of this transformation.
['Cynthia Kop', 'Aart Middeldorp', 'Thomas Sternagel']
Complexity of Conditional Term Rewriting