Categorical Combinatorics for Innocent Strategies
Authors:
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 379-388
Abstract
We show how to construct the category of games and innocent strategies from a more primitive category of games. On that category we define a comonad and monad with the former distributing over the latter. Innocent strategies are the maps in the induced two-sided Kleisli category. Thus the problematic composition of innocent strategies reflects the use of the distributive law. The composition of simple strategies, and the combinatorics of pointers used to give the comonad and monad are themselves described in categorical terms. The notions of view and of legal play arise naturally in the explanation of the distributivity. The category-theoretic perspective provides a clear discipline for the necessary combinatorics.Keywords
This publication has 21 references indexed in Scilit:
- Classical isomorphisms of typesMathematical Structures in Computer Science, 2005
- Combining a monad and a comonadTheoretical Computer Science, 2002
- Locus Solum: From the rules of logic to the logic of rulesMathematical Structures in Computer Science, 2001
- On Full Abstraction for PCF: I, II, and IIIInformation and Computation, 2000
- Game Semantics1997
- Linearity, Sharing and State: A Fully Abstract Game Semantics for Idealized Algol with Active Expressions1997
- Elementary observations on 2-categorical limitsBulletin of the Australian Mathematical Society, 1989
- The formal theory of monadsJournal of Pure and Applied Algebra, 1972
- Distributive laws1969
- Ordinal sums and equational doctrines1969