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

Department of Computer Science

9 Citations (Scopus)

37 Downloads (Pure)

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.

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

Access to Document

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

Ketema_2010_Infinitary_combinatoryFinal published version, 380 KBLicence: CC BY-ND

Cite this

@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

Access to Document

Fingerprint

Cite this