3
$\begingroup$

Famously, the denotational semantics of PCF in Scott domains is not fully abstract. But by adding the parallel or construct to PCF, a fully abstract semantics can be obtained.

Is there an analogous result for the untyped lambda calculus? Is the Scott semantics for the untyped lambda calculus with parallel or known to be fully abstract? If not, is there a similar feature that can be added to obtain a fully abstract semantics?

$\endgroup$

1 Answer 1

4
$\begingroup$

Full abstraction means that denotational equality coincides with observational equivalence (under all contexts), but that notion depends on what observations you choose. If your observation on a term is whether it admits a head-normal form, then the associated observational equivalence is called $\mathcal{H}^*$ and many fully abstract models are known for it, including Scott's original domain-theoretic model. See this paper by Flavien Breuvart for more: https://lmcs.episciences.org/1636

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.