On confluence and residuals in Cauchy convergent transfinite rewriting

TY - JOUR

T1 - On confluence and residuals in Cauchy convergent transfinite rewriting

AU - Simonsen, Jakob Grue

PY - 2004/8/16

Y1 - 2004/8/16

N2 - We show that non-collapsing orthogonal term rewriting systems do not have the transfinite Church-Rosser property in the setting of Cauchy convergence. In addition, we show that for (a transfinite version of) the Parallel Moves Lemma to hold, any definition of residual for Cauchy convergent rewriting must either part with a number of fundamental properties enjoyed by rewriting systems in the finitary and strongly convergent settings, or fail to hold for very simple rewriting systems.

AB - We show that non-collapsing orthogonal term rewriting systems do not have the transfinite Church-Rosser property in the setting of Cauchy convergence. In addition, we show that for (a transfinite version of) the Parallel Moves Lemma to hold, any definition of residual for Cauchy convergent rewriting must either part with a number of fundamental properties enjoyed by rewriting systems in the finitary and strongly convergent settings, or fail to hold for very simple rewriting systems.

KW - Cauchy convergence

KW - Church-Rosser property

KW - Infinitary rewriting

KW - Programming calculi

KW - Transfinite term rewriting

UR - http://www.scopus.com/inward/record.url?scp=2942665984&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2004.03.018

DO - 10.1016/j.ipl.2004.03.018

M3 - Journal article

AN - SCOPUS:2942665984

SN - 0020-0190

VL - 91

SP - 141

EP - 146

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -