Submitted by Mariangiola Dezani-Ciancaglini
Statement. Does easiness imply simple easiness?
Problem Origin. The problem was posed by Fabio Alessi and Mariangiola Dezani-Ciancaglini .
According to [Jacopini, 1975] a closed term is easy if, for any other closed term , the theory is consistent.
[Alessi and Lusin, 2002] introduce the notion of simple easiness: roughly a term is simple easy if given an arbitrary intersection type one can ﬁnd a suitable pre-order on types which allows to derive for . In the same paper the authors show that for each simple easy term and for each arbitrary closed term it is possible to build a -model in which the interpretations of and coincide.
Clearly each simple easy term is easy, but the vice versa is open.
Remark: The content of [Alessi et al., 2004] are some applications of simple easiness.
Solution: Alberto Carraro and Antonino Salibra announced a solution in February 2010, the solution is published in [Carraro and Salibra, 2012].
[Alessi and Lusin, 2002] Alessi, F. and Lusin, S. (2002). Simple easy terms. In van Bakel, S., editor, Intersection Types and Related Systems, volume 70 of Electronic Notes in Computer Science. Elsevier.
[Jacopini, 1975] Jacopini, G. (1975). A condition for identifying two elements of whatever model of combinatory logic. In Böhm, C., editor, -Calculus and Computer Science Theory, volume 37 of Lecture Notes in Computer Science, pages 213–219. Springer-Verlag.