Abstract

We propose a notion of complexity for oriented conditional rewrite systems
satisfying certain restrictions. This notion is realistic in the sense that
it measures not only successful computations, but also partial computations
that result in a failed rule application. A transformation to unconditional
context-sensitive rewrite systems is presented which reflects this
complexity notion, as well as a technique to derive runtime and
derivational complexity bounds for the result of this transformation.

BibTeX

@article{CKAMTS-LMCS17,
 author    = "Cynthia Kop and Aart Middeldorp and Thomas Sternagel",
 title     = "Complexity of Conditional Term Rewriting",
 journal   = "Logical Methods in Computer Science",
 volume    = 13,
 issue     = "1:6",
 pages     = "1--56",
 year      = 2017,
 doi       = "10.23638/LMCS-13(1:6)2017"
}