The Discriminating Power of Multiplicities in the Lambda-Calculus
The?-calculus with multiplicities is a refinement of the lazy?-calculus where the argument in an application comes with a multiplicity, which is an upper bound to the number of its uses. This introduces potential deadlocks in the evaluation. We study the discriminating power of this calculus over the usual?-terms. We prove in particular that the observational equivalence induced by contexts with multiplicities coincides with the equality of Levy?Longo trees associated with?-terms. This is a consequence of the characterization we give of the corresponding observational precongruence, as an intensional preorder involving?-expansion, namely, Ong's lazy Plotkin?Scott?Engeler preorder.