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 -