Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies

Jeroen Ketema; Jakob Grue Simonsen

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

Jeroen Ketema ; Jakob Grue Simonsen - Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies

lmcs:841 - Logical Methods in Computer Science, February 26, 2010, Volume 6, Issue 1 - https://doi.org/10.2168/LMCS-6(1:7)2010

Infinitary Combinatory Reduction Systems: Normalising Reduction StrategiesArticle

Authors: Jeroen Ketema ; Jakob Grue Simonsen

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 lambda calculus.

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

Source: arXiv.org:0912.4947

Volume: Volume 6, Issue 1

Published on: February 26, 2010

Imported on: October 28, 2008

Keywords: Computer Science - Logic in Computer Science, D.3.1, F.3.2, F.4.1, F.4.2

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph