Voir la notice de l'article provenant de la source Numdam
A closed λ-term M is easy if, for any other closed term N, the lambda theory generated by M = N is consistent. Recently, it has been introduced a general technique to prove the easiness of λ-terms through the semantical notion of simple easiness. Simple easiness implies easiness and allows to prove consistency results via construction of suitable filter models of λ-calculus living in the category of complete partial orderings: given a simple easy term M and an arbitrary closed term N, it is possible to build (in a canonical way) a non-trivial filter model which equates the interpretation of M and N. The question whether easiness implies simple easiness constitutes Problem 19 in the TLCA list of open problems. In this paper we negatively answer the question providing a non-empty co-r.e. (complement of a recursively enumerable) set of easy, but not simple easy, λ-terms.
Keywords: lambda calculus, easy lambda-terms, simple easy lambda-terms, filter models, ris models
@article{ITA_2012__46_2_291_0,
author = {Carraro, Alberto and Salibra, Antonino},
title = {Easy lambda-terms are not always simple},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {291--314},
publisher = {EDP-Sciences},
volume = {46},
number = {2},
year = {2012},
doi = {10.1051/ita/2012005},
mrnumber = {2931250},
zbl = {1253.03035},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012005/}
}
TY - JOUR AU - Carraro, Alberto AU - Salibra, Antonino TI - Easy lambda-terms are not always simple JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 291 EP - 314 VL - 46 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012005/ DO - 10.1051/ita/2012005 LA - en ID - ITA_2012__46_2_291_0 ER -
%0 Journal Article %A Carraro, Alberto %A Salibra, Antonino %T Easy lambda-terms are not always simple %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 291-314 %V 46 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012005/ %R 10.1051/ita/2012005 %G en %F ITA_2012__46_2_291_0
Carraro, Alberto; Salibra, Antonino. Easy lambda-terms are not always simple. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 2, pp. 291-314. doi: 10.1051/ita/2012005
Cité par Sources :