Complexity of Conditional Term Rewriting

Cynthia Kop, Aart Middeldorp, Thomas Sternagel

Logical Methods in Computer Science 13(1:6), pp. 1 – 56, 2017.


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.


  PDF |    doi:10.23638/LMCS-13(1:6)2017  |  © Creative Commons License


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"
Nach oben scrollen