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

lmcs:841 - Logical Methods in Computer Science, February 26, 2010, Volume 6, Issue 1
Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies

Authors: Ketema, Jeroen and Simonsen, Jakob Grue

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.


Source : oai:arXiv.org:0912.4947
DOI : 10.2168/LMCS-6(1:7)2010
Volume: Volume 6, Issue 1
Published on: February 26, 2010
Submitted on: October 28, 2008
Keywords: Computer Science - Logic in Computer Science,D.3.1,F.3.2,F.4.1,F.4.2


Share

Consultation statistics

This page has been seen 36 times.
This article's PDF has been downloaded 12 times.