Concrete data structures as games

Andrea Schalk, José Juan Palacios-Perez

    Research output: Contribution to journalArticlepeer-review


    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 languageEnglish
    Pages (from-to)193-210
    Number of pages17
    JournalElectronic Notes in Theoretical Computer Science
    Publication statusPublished - 7 Mar 2005


    • Concrete data structures
    • Games
    • Linear logic
    • Sequential computation


    Dive into the research topics of 'Concrete data structures as games'. Together they form a unique fingerprint.

    Cite this