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

lmcs:3123 - Logical Methods in Computer Science, February 6, 2017, Volume 13, Issue 1 - https://doi.org/10.23638/LMCS-13(1:6)2017
Complexity of Conditional Term RewritingArticle

Authors: Cynthia Kop ; Aart Middeldorp ; Thomas Sternagel

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.

Comment: This is an extended and improved version of "Conditional Complexity" as published in the proceedings of RTA 2015. It has been submitted for journal publication in LMCS

https://doi.org/10.23638/LMCS-13(1:6)2017
Source: arXiv.org:1510.07276
Volume: Volume 13, Issue 1
Published on: February 6, 2017
Imported on: February 6, 2017
Keywords: Computer Science - Logic in Computer Science, F.4.2
Licence: arXiv.org - Non-exclusive license to distribute
Funding:
    Source : OpenAIRE Graph
  • Constrained Rewriting and SMT: Emerging Trends in Rewriting; Code: I 963
  • Higher-Order Rewriting for Intensional Properties of Programs and Circuits; Funder: European Commission; Code: 658162

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 2790 times.
This article's PDF has been downloaded 871 times.