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.
Accepté le :
Publié le :
Pierre-Louis Curien 1
@article{CRMATH_2002__334_1_77_0, author = {Pierre-Louis Curien}, 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}, }
Pierre-Louis Curien. Sur l'$ \mathbf{\eta }$-expansion infinie. Comptes Rendus. Mathématique, Volume 334 (2002) no. 1, pp. 77-82. doi : 10.1016/S1631-073X(02)02095-2. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02095-2/
[1] Domains and Lambda-Calculi, Cambridge University Press, 1998
[2] The Lambda Calculus; Its Syntax and Semantics, North-Holland, 1984
[3] 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] Infinite normal forms for the λ-calculus, Proc. Symposium on λ-Calculus and Computer Science, Roma, Lect. Notes in Comput. Sci., 37, Springer-Verlag, 1975
[6] Basic lambda-calculus, Course Notes for a Summer School in Chambéry, 1996
[7] 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 :
Commentaires - Politique