Conditional Complexity
Cynthia Kop, Aart Middeldorp, and Thomas Sternagel
Proceedings of the 26th International Conference on Rewriting Techniques
and Applications (RTA 2015), Leibniz International Proceedings in
Informatics 36, pp. 223 – 240, 2015.
Abstract
We propose a notion of complexity for oriented conditional term rewrite systems. 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 latter.BibTeX Entry
@inproceedings{KMS-RTA15,
author = "Cynthia Kop and Aart Middeldorp and Thomas Sternagel",
title = "Conditional Complexity",
booktitle = "Proceedings of the 26th International Conference on Rewriting
Techniques and Applications",
editor = "Maribel Fern\'andez",
series = "Leibniz International Proceedings in Informatics"
volume = 36,
pages = "223--240",
year = 2015,
doi = "10.4230/LIPIcs.RTA.2015.223"
}