Sequential functions on indexed domains and full abstraction for a
sub-language of PCF
CMU SCS Tech reports 93-163, School of Computer Science, Carnegie Mellon
In Mathematical Foundations of Programming Semantics, Proceedings of
the Ninth International Conference, MFPS '93, New Orleans, April 1993.
Lecture Notes in Computer Science, vol 802. Springer-Verlag
Available as PostScript.
We present a general semantic framework of sequential functions on domains
equipped with a parameterized notion of incremental sequential computation.
Under the simplifying assumption that computation over function spaces
proceeds by successive application to constants, we construct a sequential
semantic model for a non-trivial sub-language of PCF with a corresponding
syntactic restriction --- that variables of function type may only be applied
to closed terms. We show that the model is fully abstract for the
sub-language, with respect to the usual notion of program behavior.
BRICS WWW home page