Geodesic
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

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.

DOI : 10.1051/ita/2012005
Classification : 03B40
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 :