Plotkin, Gordon

30

2003-11-06T11:11:11Z

2003-11-06T11:11:11Z

2003-11-06T11:11:11Z

The connection between operational and denotational semantics is of longstanding interest in the study of programming languages. One naturally seeks positive results. For example in [FP94, Sim99] adequacy results are given for models in a variety of categories. Again, the failure of full abstraction in the standard models constructed using complete partial orders and continuous functions [Plo77, Mil77] prompted the exploration of other categories (see, e.g., [BCL85, FJM96, AM98, AC98]) with varying degrees of success. In this paper we interest ourselves in counterexamples in order to make a case that these natural avenues of research had a degree of necessity. To this end, we construct inadequate models and investigate whether one can do better than the standard model, but still stay in the category of complete partial orders. (In contrast, an inadequate standard model of PCF is given in [Sim99]—but in a specially constructed category.)

270041 bytes

application/pdf

http://hdl.handle.net/1842/224

en

Laboratory for Foundations of Computer Science

Three Inadequate Models

Preprint