Complexity of conditional term rewriting

Cynthia Louisa Martina Kop; Aart Middeldorp; Thomas Sternagel

doi:10.23638/LMCS-13(1:6)2017

Complexity of conditional term rewriting

Cynthia Louisa Martina Kop, Aart Middeldorp, Thomas Sternagel

Department of Computer Science

4 Citations (Scopus)

8 Downloads (Pure)

Abstract

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

Original language	English
Article number	6
Journal	Logical Methods in Computer Science
Volume	13
Issue number	1
Number of pages	56
ISSN	1860-5974
DOIs	https://doi.org/10.23638/LMCS-13(1:6)2017
Publication status	Published - 2017

Access to Document

10.23638/LMCS-13(1:6)2017Licence: CC BY-ND

Kop_2017_Complexity_of_conditionalFinal published version, 669 KBLicence: CC BY-ND

https://lmcs.episciences.org/3123Licence: CC BY-ND

Cite this

@article{b5f72067ef9b4b41bd85594a0cde40c0,

title = "Complexity of conditional term rewriting",

abstract = "We propose a notion of complexity for oriented conditional 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.",

author = "Kop, {Cynthia Louisa Martina} and Aart Middeldorp and Thomas Sternagel",

year = "2017",

doi = "10.23638/LMCS-13(1:6)2017",

language = "English",

volume = "13",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "International Federation for Computational Logic",

number = "1",

}

TY - JOUR

T1 - Complexity of conditional term rewriting

AU - Kop, Cynthia Louisa Martina

AU - Middeldorp, Aart

AU - Sternagel, Thomas

PY - 2017

Y1 - 2017

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

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

U2 - 10.23638/LMCS-13(1:6)2017

DO - 10.23638/LMCS-13(1:6)2017

M3 - Journal article

SN - 1860-5974

VL - 13

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 1

M1 - 6

ER -

Complexity of conditional term rewriting

Abstract

Access to Document

Fingerprint

Cite this