✦ LIBER ✦

There is no fully abstract fixpoint semantics for non-deterministic languages with infinite computations

✍ Scribed by Sven-Olof Nyström

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 456 KB
Volume: 60
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00177-9

No coin nor oath required. For personal study only.

✦ Synopsis

It is well known that for many non-deterministic programming languages there is no continuous fully abstract fixpoint semantics. This is usually attributed to "problems with continuity", that is, the assumption that the semantic functions should be continuous supposedly plays a role in the difficulties of giving a fully abstract fixpoint semantics. We show that for a large class of non-deterministic programming languages there is no fully abstract least fixpoint semantics even if one considers arbitrary functions (not necessarily continuous) over arbitrary partial orders (not necessarily complete).