[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
Originator: Jan Willem Klop
Date: December 1991
Summary: Prove a Parallel Moves Lemma for reductions of infinite length.
For reductions of transfinite length, a version of the Parallel Moves Lemma can be proved if one considers only “strongly converging” infinite reductions in the sense of [KKSd91]. However, if one wants to consider converging reductions, as in [DKP91], then it is not difficult to construct a counterexample, not to the infinite Parallel Moves Lemma itself, but to the method of proof (cf. [KKSd90]). An infinite Parallel Moves Lemma might involve a different notion of “descendant”.
[Sim04] shows that it is not possible to obtain a Parallel Moves Lemma for (Cauchy-)convergent infinite reductions which relies on a notion of residual maintaining some of the basic properties of residuals known from the finite case. His counterexamples, however, are somewhat particular in that the right-hand sides of the rewrite rule are not normalized. The question remains whether it is possible to salvage a Parallel Moves Lemma for (Cauchy-)convergent reductions for restricted classes of rewrite systems.
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |