We present a new and formal coinductive proof of confluence and normalisation of B "ohm reduction in infinitary lambda calculus. The proof is simpler than previous proofs of this result. The technique of the proof is new, i.e., it is not merely a coinductive reformulation of any earlier proofs. We formalised the proof in the Coq proof assistant.
Joachimski in @cite_14 gives a coinductive confluence proof for infinitary lambda calculus, but Joachimski's notion of reduction does not correspond to the standard notion of a strongly convergent reduction. Essentially, it allows for infinitely many parallel contractions in one step, but only finitely many reduction steps. The coinductive definition of infinitary reductions capturing strongly convergent reductions was introduced in @cite_8 . Later @cite_10 @cite_32 generalised this to infinitary term rewriting systems. @cite_16 using the definition from @cite_8 , confluence of infinitary lambda calculus modulo equivalence of root-active subterms was shown coinductively. The proof in @cite_16 follows the general strategy of @cite_12 @cite_4 . The proof in the present paper bears some similarity to the proof of the unique normal forms property of orthogonal iTRSs in @cite_25 . It is also similar to the coinductive confluence proof for nearly orthogonal infinitary term rewriting systems in @cite_20 , but there the standard'' reduction employed is not unique and need not be normalising.
@cite_14 @cite_4 @cite_8 @cite_20 @cite_32 @cite_16 @cite_10 @cite_25 @cite_12
2316213087 2403774400 1994588735 1976336764
We give a relatively simple coinductive proof of confluence, modulo equivalence of root-active terms, of nearly orthogonal infinitary term rewriting systems. Nearly orthogonal systems allow certain root overlaps, but no non-root overlaps. Using a slightly more complicated method we also show confluence modulo equivalence of hypercollapsing terms. The condition we impose on root overlaps is similar to the condition used by Toyama in the context of finitary rewriting. We provide a coinductive definition of strongly convergent reductions between infinite lambda terms. This approach avoids the notions of ordinals and metric convergence which have appeared in the earlier definitions of the concept. As an illustration, we prove the existence part of the infinitary standardization theorem. The proof is fully formalized in Coq using coinductive types. The paper concludes with a characterization of infinite lambda terms which reduce to themselves in a single beta step. We define infinitary Combinatory Reduction Systems (iCRSs), thus providing the first notion of infinitary higher-order rewriting. The systems defined are sufficiently general that ordinary infinitary term rewriting and infinitary @l-calculus are special cases. Furthermore, we generalise a number of known results from first-order infinitary rewriting and infinitary @l-calculus to iCRSs. In particular, for fully-extended, left-linear iCRSs we prove the well-known compression property, and for orthogonal iCRSs we prove that (1) if a set of redexes U has a complete development, then all complete developments of U end in the same term and that (2) any tiling diagram involving strongly convergent reductions S and T can be completed iff at least one of S T and T S is strongly convergent. We also prove an ancillary result of independent interest: a set of redexes in an orthogonal iCRS has a complete development iff the set has the so-called finite jumps property. We show the existence of an infinitary confluen t and normalising extension of the finite extensional lambda calculus with beta and eta. Besides infinite beta reductions also infinite eta reductions are possible in this extension, and terms without head normal form can be reduced to bottom. As corollaries we obtain a simple, syntax based construction of an extensional Bohm model of the finite lambda calculus; and a simple, syntax based proof that two lambda terms have the same semantics in this model if and only if theyha ve the same eta-Bohm tree if and only if they are observationally equivalent wrt to beta normal forms. The confluence proof reduces confluence of beta, bottom and eta via infinitary commutation and postponement arguments to confluence of beta and bottom and confluence of eta.We give counterexamples against confluence of similar extensions based on the identification of the terms without weak head normal form and the terms without top normal form (rootactive terms) respectively.