Nondeterminism in Game Semantics via Sheaves

Abstract

Harmer and McCusker have developed a fully abstract game model for nondeterministic Idealised Algol and, at the same time, revealed difficulties in constructing game models for stateless nondeterministic languages and infinite nondeterminism. We propose a novel approach in which a strategy is not a set, but a tree, of plays, and develop a fully abstract game model for a nondeterministic stateless language. Mathematically such a strategy is formalised as a sheaf over an appropriate site of plays. We conclude with a study on the difficulties pointed out by Harmer and McCusker in terms of the structure of the coverage of the sites.