Skip to main content

Making parallel-or deterministic again

Pierre Clairambault ( CNRS & ENS Lyon )

Although Plotkin’s parallel-or is inherently deterministic, it has a
non-deterministic interpretation in games based on (prime) event
structures – in which an event has a unique causal history – because
they do not directly support disjunctive causality. General event
structures can express disjunctive causality and have a more permissive
notion of determinism, but do not support hiding. We show that
(structures equivalent to) deterministic general event structures do
support hiding, and construct a new category of games based on them with
a deterministic interpretation of an affine variant of PCF extended with
parallel-or. We then exploit this deterministic interpretation to give a
relaxed notion of determinism (observable determinism) on the plain
event structures model. Putting this together with our previously
introduced concurrent notions of well-bracketing and innocence, we
obtain an intensionally fully abstract model for our language.

This is joint work with Simon Castellan and Glynn Winskel, presented at
FSCD 2017.



Share this: