Graphical Foundations for Dialogue Games

  • Cai Wingfield

Student thesis: Doctoral ThesisPhD

Abstract

In the 1980s and 1990s, Joyal and Street developed a graphical notation for various flavours of monoidal category using graphs drawn in the plane, commonly known as string diagrams. In particular, their work comprised a rigorous topological foundation of the notation.In 2007, Harmer, Hyland and Melliès gave a formal mathematical foundation for game semantics using a notions they called ⊸-schedules, ⊗-schedules and heaps. Schedules described interleavings of plays in games formed using ⊸ and ⊗, and heaps provided pointers used for backtracking. Their definitions were combinatorial in nature, but researchers often draw certain pictures when working in practice.In this thesis, we extend the framework of Joyal and Street to give a formal account of the graphical methods already informally employed by researchers in game semantics. We give a geometric formulation of ⊸-schedules and ⊗-schedules, and prove that the games they describe are isomorphic to those described in Harmer et al.’s terms, and also those given by a more general graphical representation of interleaving across games of multiple components. We further illustrate the value of the geometric methods by demonstrating that several proofs of key properties (such as that the composition of ⊸-schedules is associative) can be made straightforward, reflecting the geometry of the plane, and overstepping some of the cumbersome combinatorial detail of proofs in Harmer et al.’s terms. We further extend the framework of formal plane diagrams to account for the heaps and pointer structures used in the backtracking functors for O and P.
Date of Award31 Dec 2013
LanguageEnglish
Awarding Institution
  • University of Bath
SponsorsEngineering and Physical Sciences Research Council
SupervisorGuy McCusker (Supervisor) & Anthony Power (Supervisor)

Keywords

  • game semantics
  • category theory
  • graphical methods
  • composites
  • associativity
  • dialogue games
  • symmetric monoidal closed
  • exponentials

Cite this

Graphical Foundations for Dialogue Games
Wingfield, C. (Author). 31 Dec 2013

Student thesis: Doctoral ThesisPhD