Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A graphical foundation for interleaving in game semantics
AU - McCusker, Guy
AU - Power, John
AU - Wingfield, Cai
PY - 2015/4/1
Y1 - 2015/4/1
N2 - In 2007, Harmer, Hyland and Melliès gave a formal mathematical foundation for game semantics using a notion they called a {multimap}-schedule, and the similar notion of ⊗-schedule, both structures describing interleavings of plays in games. Their definition was combinatorial in nature, but researchers often draw pictures when describing schedules in practice. Moreover, several proofs of key properties, such as that the composition of {multimap}-schedules is associative, involve cumbersome combinatorial detail, whereas in terms of pictures the proof is straightforward, reflecting the geometry of the plane. Here, we give a geometric formulation of {multimap}-schedules and ⊗-schedules, prove that they are isomorphic to Harmer et al.'s definitions, and illustrate their value by giving such geometric proofs. Harmer et al.'s notions may be combined to describe plays in multi-component games, and researchers have similarly developed intuitive graphical representations of plays in these games. We give a characterisation of these diagrams and explicitly describe how they relate to the underlying schedules, finally using this relation to provide new, intuitive proofs of key categorical properties.
AB - In 2007, Harmer, Hyland and Melliès gave a formal mathematical foundation for game semantics using a notion they called a {multimap}-schedule, and the similar notion of ⊗-schedule, both structures describing interleavings of plays in games. Their definition was combinatorial in nature, but researchers often draw pictures when describing schedules in practice. Moreover, several proofs of key properties, such as that the composition of {multimap}-schedules is associative, involve cumbersome combinatorial detail, whereas in terms of pictures the proof is straightforward, reflecting the geometry of the plane. Here, we give a geometric formulation of {multimap}-schedules and ⊗-schedules, prove that they are isomorphic to Harmer et al.'s definitions, and illustrate their value by giving such geometric proofs. Harmer et al.'s notions may be combined to describe plays in multi-component games, and researchers have similarly developed intuitive graphical representations of plays in these games. We give a characterisation of these diagrams and explicitly describe how they relate to the underlying schedules, finally using this relation to provide new, intuitive proofs of key categorical properties.
U2 - 10.1016/j.jpaa.2014.05.040
DO - 10.1016/j.jpaa.2014.05.040
M3 - Journal article
AN - SCOPUS:84916219862
VL - 219
SP - 1131
EP - 1174
JO - Journal of Pure and Applied Algebra
JF - Journal of Pure and Applied Algebra
SN - 0022-4049
IS - 4
ER -