Infinitary combinatory reduction systems: normalising reduction strategies

Jeroen Ketema; Jakob Grue Simonsen

doi:10.2168/LMCS-6(1:7)2010

Infinitary combinatory reduction systems: normalising reduction strategies

Jeroen Ketema, Jakob Grue Simonsen

Datalogisk Institut

9 Citationer (Scopus)

37 Downloads (Pure)

Abstract

We study normalising reduction strategies for infinitary Combinatory Reduc-
tion Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary -calculus.

Originalsprog	Engelsk
Artikelnummer	7
Tidsskrift	Logical Methods in Computer Science
Vol/bind	6
Udgave nummer	1
Antal sider	35
ISSN	1860-5974
DOI	https://doi.org/10.2168/LMCS-6(1:7)2010
Status	Udgivet - 2010

Adgang til dokumentet

10.2168/LMCS-6(1:7)2010Licens: CC BY-ND

Ketema_2010_Infinitary_combinatoryForlagets udgivne version, 380 KBLicens: CC BY-ND

Citationsformater

@article{4fccabe61968491399b3135eebeb4c39,

title = "Infinitary combinatory reduction systems: normalising reduction strategies",

abstract = "We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary λ-calculus.",

author = "Jeroen Ketema and Simonsen, {Jakob Grue}",

year = "2010",

doi = "10.2168/LMCS-6(1:7)2010",

language = "English",

volume = "6",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "International Federation for Computational Logic",

number = "1",

}

TY - JOUR

T1 - Infinitary combinatory reduction systems

T2 - normalising reduction strategies

AU - Ketema, Jeroen

AU - Simonsen, Jakob Grue

PY - 2010

Y1 - 2010

N2 - We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary λ-calculus.

AB - We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary λ-calculus.

U2 - 10.2168/LMCS-6(1:7)2010

DO - 10.2168/LMCS-6(1:7)2010

M3 - Journal article

SN - 1860-5974

VL - 6

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 1

M1 - 7

ER -

Infinitary combinatory reduction systems: normalising reduction strategies

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater