On confluence and residuals in Cauchy convergent transfinite rewriting

Jakob Grue Simonsen

doi:10.1016/j.ipl.2004.03.018

On confluence and residuals in Cauchy convergent transfinite rewriting

Jakob Grue Simonsen^*

^*Corresponding author af dette arbejde

Datalogisk Institut

11 Citationer (Scopus)

Abstract

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.

Originalsprog	Engelsk
Tidsskrift	Information Processing Letters
Vol/bind	91
Udgave nummer	3
Sider (fra-til)	141-146
Antal sider	6
ISSN	0020-0190
DOI	https://doi.org/10.1016/j.ipl.2004.03.018
Status	Udgivet - 16 aug. 2004

Adgang til dokumentet

10.1016/j.ipl.2004.03.018

Andre filer og links

Link to publication in Scopus

Citationsformater

Simonsen, J. G. (2004). On confluence and residuals in Cauchy convergent transfinite rewriting. Information Processing Letters, 91(3), 141-146. https://doi.org/10.1016/j.ipl.2004.03.018

@article{64637d40cfc74ae885ffa3097f04e5ae,

title = "On confluence and residuals in Cauchy convergent transfinite rewriting",

abstract = "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.",

keywords = "Cauchy convergence, Church-Rosser property, Infinitary rewriting, Programming calculi, Transfinite term rewriting",

author = "Simonsen, {Jakob Grue}",

year = "2004",

month = aug,

day = "16",

doi = "10.1016/j.ipl.2004.03.018",

language = "English",

volume = "91",

pages = "141--146",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

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 -

On confluence and residuals in Cauchy convergent transfinite rewriting

Abstract

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater