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

@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"
}