cl-banner

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.

 

  PDF |    doi:10.4230/LIPIcs.RTA.2015.223  |  © Creative Commons License – CC   BY

BibTeX 

@inproceedings{CKAMTS-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 (RTA 2015)",
editor = "Maribel Fern{\'a}ndez",
series = "Leibniz International Proceedings in Informatics"
volume = 36,
pages = "223--240",
year = 2015,
doi = "10.4230/LIPIcs.RTA.2015.223"
}
Nach oben scrollen