Kop, Cynthia and Middeldorp, Aart and Sternagel, Thomas - Complexity of Conditional Term Rewriting

lmcs:3123 - Logical Methods in Computer Science, February 6, 2017, Volume 13, Issue 1
Complexity of Conditional Term Rewriting

Authors: Kop, Cynthia and Middeldorp, Aart and Sternagel, Thomas

We propose a notion of complexity for oriented conditional term 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.


Source : oai:arXiv.org:1510.07276
DOI : 10.23638/LMCS-13(1:6)2017
Volume: Volume 13, Issue 1
Published on: February 6, 2017
Submitted on: February 6, 2017
Keywords: Computer Science - Logic in Computer Science,F.4.2


Share

Consultation statistics

This page has been seen 298 times.
This article's PDF has been downloaded 150 times.