Confluency property of the call-by-value µ ^_ -calculus
Karim Nour, Khelifa Saber · 2006
Gentzen (1955) introduced the natural deduction system to study the notion of proof. The full classical natural deduction system is well adapted for the human reasoning. By full we mean that all the connectives (→, ∧ and ∨) and ⊥ (for the absurdity) are considered as primitive. As usual, the negation is defined by ¬A = A → ⊥. Considering this logic from the computer science of view is interesting because, by the Curry-Howard correspondence, formulas can be seen as types for the functional programming languages and correct programs can be extracted. The corresponding calculus is an extension of M. Parigot’s λμcalculus with product and coproduct, which is denoted by λμ∧∨-calculus. De Groote (2001) introduced the typed λμ∧∨-calculus to code the classical natural deduction system, and showed that it enjoys the main important properties: the strong normalization, the confluence and the subformula property. This would guarantee that proof normalization may be interpreted as an evaluation process. As far as we know the typed λμ∧∨-calculus is the first extension of the simply typed λ-calculus which enjoys all the above properties. Ritter et al. (2000a) introduced an extension of the λμ-calculus that features disjunction as primitive (see also Ritter et al. (2000b)). But their system is rather different since they take as primitive a classical form of disjunction that amounts to ¬A→ B. Nevertheless, Ritter and Pym (2001) give another extension of the λμ-calculus with an intuitionistic disjunction. However, the reduction rules considered are not sufficient to guarantee that the normal forms satisfy the subformula property. The question of the strong normalization of the full logic has interested several authors, thus one finds in David and Nour (2003), Matthes (2005) and Nour and Saber (2005) different proofs of this result. From a computer science point of view, the λμ∧∨-calculus may be seen as the kernel of a typed call-byname functional language featuring product, coproduct and control operators. However we cannot apply