Concurrent Structures in Game Semantics
File(s)eatcs.pdf (216.68 KB)
Published version
Author(s)
Castellan, SPA
Type
Journal Article
Abstract
Game semantics is a powerful tool to design intensional denotational
semantics of complex programming languages, leading to notions of syntaxfree
normal forms and fully abstract models. In game semantics, programs
become strategies, ie. set of plays, on a game given by their type.
Traditionally, game semantics represents plays as sequences of moves.
This representation forces to reduce concurrency to interleavings. In this
paper, we develop a framework of game semantics based on event structures
– a partial order representation of concurrency, extending the work of
Rideau and Winskel [19]. This causal representation allows to retain more
intensional behaviour on concurrent programs. We demonstrate the benefits
of this approach by developing a notion of concurrent and nondeterministic
innocence, which an open problem despite the existence of many game semantics
models of concurrent languages. We show that, our innocence along
with an extension of well-bracketing, can capture the essence of parallel and
nondeterministic computation.
semantics of complex programming languages, leading to notions of syntaxfree
normal forms and fully abstract models. In game semantics, programs
become strategies, ie. set of plays, on a game given by their type.
Traditionally, game semantics represents plays as sequences of moves.
This representation forces to reduce concurrency to interleavings. In this
paper, we develop a framework of game semantics based on event structures
– a partial order representation of concurrency, extending the work of
Rideau and Winskel [19]. This causal representation allows to retain more
intensional behaviour on concurrent programs. We demonstrate the benefits
of this approach by developing a notion of concurrent and nondeterministic
innocence, which an open problem despite the existence of many game semantics
models of concurrent languages. We show that, our innocence along
with an extension of well-bracketing, can capture the essence of parallel and
nondeterministic computation.
Date Issued
2017-10-31
Date Acceptance
2017-10-15
Citation
Bulletin of the European Association for Theoretical Computer Science, 2017, 123
ISSN
0252-9742
Publisher
European Association for Theoretical Computer Science
Journal / Book Title
Bulletin of the European Association for Theoretical Computer Science
Volume
123
Copyright Statement
© European Association for Theoretical Computer Science
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Grant Number
ERI 025567 (EP/K034413/1)
EP/K011715/1
Subjects
0802 Computation Theory And Mathematics
Publication Status
Published
Date Publish Online
2017-11-15