Full abstraction for Gamma

Abstract

Gamma is a simple, but powerful, parallel programming language. Its only data structure is the multiset or bag. Banatre and Metayer proposed the language as a means to derive sistematically programs in the spirit of Dijkstra's discipline of programming. It has been applied to solve problems in scheduling, image processing and fractal generation. Different operational semantics models for Gamma have been proposed. We single out one of them and also produce a denotational semantics for which full abstraction is proven with respect to the operational model chosen. The result can be used as a basis for a further proof system for Gamma.