Geodesic
Sur l'η-expansion infinie
Curien, Pierre-Louis1
1 PPS, case 7014, CNRS & Université Paris-7, 2, place Jussieu, 75251 Paris cedex 05, France
Comptes Rendus. Mathématique, Tome 334 (2002) no. 1, pp. 77-82.

Voir la notice de l'article provenant de la source Numdam

Nous donons deux caractérisations de l'ordre sur les arbres de Böhm induit par le modèle D∞, dont l'une est nouvelle et formalise une propriété de continuité de l'η-expansion infinie : 𝒜⪯ ^ ∞ ℬ si pour tout approximant fini A de 𝒜, il existe un approximant fini B de ℬ tel que A est un sous-arbre de B, modulo une η-égalité finie et modulo un nombre fini d'η-expansions infinies de variables.

We give two characterizations of the ordering on Böhm trees induced by the D∞ model, one of which formalizes a continuity property of infinite η-expansion: 𝒜⪯ ^ ∞ ℬ if for any finite approximant A of 𝒜 there exists a finite approximant B of ℬ such that A is a sub-tree of B, modulo finitely many η-equalities and finitely many infinite η-expansions of variables.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(02)02095-2

Curien, Pierre-Louis 1

1 PPS, case 7014, CNRS & Université Paris-7, 2, place Jussieu, 75251 Paris cedex 05, France 
@article{CRMATH_2002__334_1_77_0,
     author = {Curien, Pierre-Louis},
     title = {Sur l'$ \mathbf{\eta }$-expansion infinie},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {77--82},
     publisher = {Elsevier},
     volume = {334},
     number = {1},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02095-2},
     language = {fr},
     url = {http://geodesic.mathdoc.fr/articles/10.1016/S1631-073X(02)02095-2/}
}
TY  - JOUR
AU  - Curien, Pierre-Louis
TI  - Sur l'$ \mathbf{\eta }$-expansion infinie
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 77
EP  - 82
VL  - 334
IS  - 1
PB  - Elsevier
UR  - http://geodesic.mathdoc.fr/articles/10.1016/S1631-073X(02)02095-2/
DO  - 10.1016/S1631-073X(02)02095-2
LA  - fr
ID  - CRMATH_2002__334_1_77_0
ER  - 
%0 Journal Article
%A Curien, Pierre-Louis
%T Sur l'$ \mathbf{\eta }$-expansion infinie
%J Comptes Rendus. Mathématique
%D 2002
%P 77-82
%V 334
%N 1
%I Elsevier
%U http://geodesic.mathdoc.fr/articles/10.1016/S1631-073X(02)02095-2/
%R 10.1016/S1631-073X(02)02095-2
%G fr
%F CRMATH_2002__334_1_77_0
Curien, Pierre-Louis. Sur l'$ \mathbf{\eta }$-expansion infinie. Comptes Rendus. Mathématique, Tome 334 (2002) no. 1, pp. 77-82. doi : 10.1016/S1631-073X(02)02095-2. http://geodesic.mathdoc.fr/articles/10.1016/S1631-073X(02)02095-2/

[1] Amadio, R.; Curien, P.-L. Domains and Lambda-Calculi, Cambridge University Press, 1998

[2] Barendregt, H. The Lambda Calculus; Its Syntax and Semantics, North-Holland, 1984

[3] Hyland, M. A syntactic characterization of the equality in some models of lambda calculus, J. London Math. Soc., Volume 2 (1976), pp. 361-370

[4] Lévy J.-J., Propriétés syntaxiques du λ-Calcul, Rapport Technique LITP 79-11, Université Paris-7, 1979

[5] Nakajima, R. Infinite normal forms for the λ-calculus, Proc. Symposium on λ-Calculus and Computer Science, Roma, Lect. Notes in Comput. Sci., 37, Springer-Verlag, 1975

[6] Ronchi della Rocca, S. Basic lambda-calculus, Course Notes for a Summer School in Chambéry, 1996

[7] Wadsworth, C. The relation between computational and denotational properties for Scott's D-infinity models of the lambda-calculus, SIAM J. Comput., Volume 5 (1976), pp. 488-521

Cité par Sources :