×

Polarized proof-nets and \(\lambda \mu\)-calculus. (English) Zbl 1019.68021

Summary: We first define polarized proof-nets, an extension of MELL proof-nets for the polarized fragment of linear logic; the main difference with usual proof-nets is that we allow structural rules on any negative formula. The essential properties (confluence, strong normalization in the typed case) of polarized proof-nets are proved using a reduction preserving translation into usual proof-nets. We then give a reduction preserving encoding of Parigot’s \(\lambda \mu\)-terms for classical logic as polarized proof-nets. It is based on the intuitionistic translation: \(A\rightarrow B\), so that it is a straightforward extension of the usual translation of \(\lambda\)-calculus into proof-nets. We give a reverse encoding which sequentializes any polarized proof-net as a \(\lambda \mu\)-term. In the last part of the paper, we extend the \(\sigma\)-equivalence for \(\lambda\)-calculus to \(\lambda \mu\)-calculus. Interestingly, this new \(\sigma\)-equivalence relation identifies normal \(\lambda \mu\)-terms. We eventually show that two terms are equivalent iff they are translated as the same polarized proof-net; thus the set of polarized proof-nets represents the quotient of \(\lambda \mu\)-calculus by \(\sigma\)-equivalence.

MSC:

68N18 Functional programming and lambda calculus
03B40 Combinatory logic and lambda calculus
03F07 Structure of proofs
03F52 Proof-theoretic aspects of linear logic and other substructural logics
Full Text: DOI

References:

[1] V. Danos, La logique linéaire appliquée à l’étude de divers processus de normalisation (principalement du \(λ\); V. Danos, La logique linéaire appliquée à l’étude de divers processus de normalisation (principalement du \(λ\)
[2] Danos, V.; Regnier, L., Proof-nets and the Hilbert space, (Girard, J.-Y.; Lafont, Y.; Regnier, L., Advances in Linear Logic. Advances in Linear Logic, London Mathematical Society Lecture Note Series, Vol. 222 (1995), Cambridge University Press: Cambridge University Press Cambridge), 307-328 · Zbl 0854.03011
[3] Danos, V.; Joinet, J.-B.; Schellinx, H., A new deconstructive logiclinear logic, J. Symbolic Logic, 62, 3, 755-807 (1997) · Zbl 0895.03023
[4] R. David, W. Py, λμ; R. David, W. Py, λμ · Zbl 0981.03019
[5] Girard, J.-Y., A new constructive logic: classical logic, Math. Struct. Comput. Sci., 1, 3, 255-296 (1991) · Zbl 0752.03027
[6] J.-L. Krivine, Un interpréteur du lambda-calcul, unpublished. URL; J.-L. Krivine, Un interpréteur du lambda-calcul, unpublished. URL
[7] O. Laurent, Logique linéaire polarisée et logiques classiques, Mémoire du magistère M.M.F.A.I., Ecole Normale Supérieure de Paris, September, 1999. URL; O. Laurent, Logique linéaire polarisée et logiques classiques, Mémoire du magistère M.M.F.A.I., Ecole Normale Supérieure de Paris, September, 1999. URL
[8] Laurent, O., Polarized proof-nets: proof-nets for LC (extended abstract), (Girard, J.-Y., Typed Lambda Calculi and Applications ’99. Typed Lambda Calculi and Applications ’99, Lecture Notes in Computer Science, Vol. 1581 (1999), Springer: Springer Berlin), 213-227 · Zbl 0933.03081
[9] Parigot, M., λμ-calculusan algorithmic interpretation of classical natural deduction, (Proc. Internat. Conf. on Logic Programming and Automated Deduction. Proc. Internat. Conf. on Logic Programming and Automated Deduction, Lecture Notes in Computer Science, Vol. 624 (1992), Springer: Springer Berlin), 190-201 · Zbl 0925.03092
[10] Parigot, M., Classical proofs as programs, (Proceedings of Kurt Gödel Colloquium. Proceedings of Kurt Gödel Colloquium, Lecture Notes in Computer Science, Vol. 713 (1993), Springer: Springer Berlin), 263-276 · Zbl 0805.03012
[11] Quatrini, M.; Tortora de Falco, L., Polarisation des preuves classiques et renversement, Compte-Rendu de l’Académie des Sciences de Paris, 323, 113-116 (1996) · Zbl 0862.03030
[12] L. Regnier, Lambda-calcul et réseaux, Thèse de doctorat, Université Paris VII, 1992.; L. Regnier, Lambda-calcul et réseaux, Thèse de doctorat, Université Paris VII, 1992.
[13] Regnier, L., Une équivalence sur les lambda-termes, Theoret. Comput. Sci., 126, 281-292 (1994) · Zbl 0801.03013
[14] P. Selinger, Control categories and duality: on the categorical semantics of the lambda-mu calculus, Math. Struct. Comput. Sci. 11 (2) (2001) 207-260, to appear, URL; P. Selinger, Control categories and duality: on the categorical semantics of the lambda-mu calculus, Math. Struct. Comput. Sci. 11 (2) (2001) 207-260, to appear, URL · Zbl 0984.18003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.