Concrete data structures as games

Andrea Schalk, José Juan Palacios-Perez

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 languageEnglish
    Title of host publicationElectronic Notes in Theoretical Computer Science|Electron. Notes Theor. Comput. Sci.
    EditorsL. Birkedal
    Pages193-210
    Number of pages17
    Volume122
    DOIs
    Publication statusPublished - 7 Mar 2005
    EventProceedings 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

    ConferenceProceedings of the 10th Conference on Category Theory in Computer Science (CTCS 2004)
    Period7/03/05 → …
    Internet address

    Keywords

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

    Fingerprint

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

    Cite this