Complexity of Conditional Term Rewriting

We propose a notion of complexity for oriented conditional term rewritesystems satisfying certain restrictions. This notion is realistic in the sensethat it measures not only successful computations, but also partialcomputations that result in a failed rule application. A transformation tounconditional context-sensitive rewrite systems is presented which reflectsthis complexity notion, as well as a technique to derive runtime andderivational complexity bounds for the result of this transformation.Comment: This is an extended and improved version of "Conditional Complexity" as published in the proceedings of RTA 2015. It has been submitted for journal publication in LMC