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 Rewriting

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.


    Volume: Volume 13, Issue 1
    Published on: February 6, 2017
    Accepted on: February 6, 2017
    Submitted on: February 6, 2017
    Keywords: Computer Science - Logic in Computer Science,F.4.2
    Fundings :
      Source : OpenAIRE Graph
    • Constrained Rewriting and SMT: Emerging Trends in Rewriting; Funder: Austrian Science Fund (FWF); Code: I 963

    Linked data

    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.fscd.2021.31
    Source : ScholeXplorer IsCitedBy HANDLE 2066/236638
    • 10.4230/lipics.fscd.2021.31
    • 2066/236638
    • 2066/236638
    Tuple Interpretations for Higher-Order Complexity
    Kop, C. ; Vale, D. ; Kobayashi, N. ;

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 934 times.
    This article's PDF has been downloaded 324 times.