Abstract
A result by Curien establishes that filiform concrete data structures can be viewed as games. We extend the idea to cover all stable concrete data structures. This necessitates a theory of games with an equivalence relation on positions. We present a faithful functor from the category of concrete data structures to this new category of games, allowing a game-like reading of the former. It is possible to restrict to a cartesian closed subcategory of these games, where the function space does not decompose and the product is given by the usual tensor product construction. There is a close connection between these games and graph games. © 2005 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Title of host publication | Electronic Notes in Theoretical Computer Science|Electron. Notes Theor. Comput. Sci. |
| Editors | L. Birkedal |
| Pages | 193-210 |
| Number of pages | 17 |
| Volume | 122 |
| DOIs | |
| Publication status | Published - 7 Mar 2005 |
| Event | Proceedings of the 10th Conference on Category Theory in Computer Science (CTCS 2004) - Duration: 7 Mar 2005 → … http://dblp.uni-trier.de/db/conf/galop/galop2005.html#Schalk05http://dblp.uni-trier.de/rec/bibtex/conf/galop/Schalk05.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/galop/Schalk05 |
Conference
| Conference | Proceedings of the 10th Conference on Category Theory in Computer Science (CTCS 2004) |
|---|---|
| Period | 7/03/05 → … |
| Internet address |
Keywords
- Concrete data structures
- Games
- Linear logic
- Sequential computation