Full Abstraction Without Synchronization Primitives
Andrzej S. Murawski · Electronic Notes in Theoretical Computer Science · 2010
Using game semantics, we prove a full abstraction result (with respect to the may-testing preorder) for Idealized Algol augmented with parallel composition (IA||). Although it is common knowledge that semaphores can be implemented using shared memory, we find that semaphores do not extend IA|| conservatively. We explain the reasons for the mismatch.