Concrete data structures as games

Andrea Schalk; José Juan Palacios-Perez

doi:10.1016/j.entcs.2004.06.058

Concrete data structures as games

Andrea Schalk, José Juan Palacios-Perez

Research output: Contribution to journal › Article › peer-review

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
Pages (from-to)	193-210
Number of pages	17
Journal	Electronic Notes in Theoretical Computer Science
Volume	122
DOIs	https://doi.org/10.1016/j.entcs.2004.06.058
Publication status	Published - 7 Mar 2005

Keywords

Concrete data structures
Games
Linear logic
Sequential computation

Access to Document

10.1016/j.entcs.2004.06.058

Cite this

@article{0f61634685a84c8cad778ff8d897c289,

title = "Concrete data structures as games",

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. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

keywords = "Concrete data structures, Games, Linear logic, Sequential computation",

author = "Andrea Schalk and Palacios-Perez, {Jos{\'e} Juan}",

year = "2005",

month = mar,

day = "7",

doi = "10.1016/j.entcs.2004.06.058",

language = "English",

volume = "122",

pages = "193--210",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Concrete data structures as games

AU - Schalk, Andrea

AU - Palacios-Perez, José Juan

PY - 2005/3/7

Y1 - 2005/3/7

N2 - 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.

AB - 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.

KW - Concrete data structures

KW - Games

KW - Linear logic

KW - Sequential computation

U2 - 10.1016/j.entcs.2004.06.058

DO - 10.1016/j.entcs.2004.06.058

M3 - Article

SN - 1571-0661

VL - 122

SP - 193

EP - 210

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

ER -

Concrete data structures as games

Abstract

Keywords

Access to Document

Fingerprint

Cite this