Constructing differential categories and deconstructing categories of games

Jim Laird, Giulio Manzonetto, Guy McCusker

Research output: Chapter in Book/Report/Conference proceedingChapter

  • 3 Citations

Abstract

We present an abstract construction for building differential categories useful to model resource sensitive calculi, and we apply it to categories of games. In one instance, we recover a category previously used to give a fully abstract model of a nondeterministic imperative language. The construction exposes the differential structure already present in this model. A second instance corresponds to a new Cartesian differential category of games. We give a model of a Resource PCF in this category and show that it enjoys the finite definability property. Comparison with a relational semantics reveals that the latter also possesses this property and is fully abstract.
LanguageEnglish
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
EditorsLuca Aceto, Monika Henzinger, Jiri Sgall
Place of PublicationHeidelberg, Germany
PublisherSpringer
Pages186-197
Number of pages12
ISBN (Print)9783642220111
DOIs
StatusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6756

Fingerprint

Game
Resources
Definability
Cartesian
Model
Calculus

Cite this

Laird, J., Manzonetto, G., & McCusker, G. (2011). Constructing differential categories and deconstructing categories of games. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings (pp. 186-197). (Lecture Notes in Computer Science; Vol. 6756). Heidelberg, Germany: Springer. DOI: 10.1007/978-3-642-22012-8_14

Constructing differential categories and deconstructing categories of games. / Laird, Jim; Manzonetto, Giulio; McCusker, Guy.

Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. ed. / Luca Aceto; Monika Henzinger; Jiri Sgall. Heidelberg, Germany : Springer, 2011. p. 186-197 (Lecture Notes in Computer Science; Vol. 6756).

Research output: Chapter in Book/Report/Conference proceedingChapter

Laird, J, Manzonetto, G & McCusker, G 2011, Constructing differential categories and deconstructing categories of games. in L Aceto, M Henzinger & J Sgall (eds), Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. Lecture Notes in Computer Science, vol. 6756, Springer, Heidelberg, Germany, pp. 186-197. DOI: 10.1007/978-3-642-22012-8_14
Laird J, Manzonetto G, McCusker G. Constructing differential categories and deconstructing categories of games. In Aceto L, Henzinger M, Sgall J, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. Heidelberg, Germany: Springer. 2011. p. 186-197. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-642-22012-8_14
Laird, Jim ; Manzonetto, Giulio ; McCusker, Guy. / Constructing differential categories and deconstructing categories of games. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. editor / Luca Aceto ; Monika Henzinger ; Jiri Sgall. Heidelberg, Germany : Springer, 2011. pp. 186-197 (Lecture Notes in Computer Science).
@inbook{d4f5530e1e2a434e923431b96ff4386e,
title = "Constructing differential categories and deconstructing categories of games",
abstract = "We present an abstract construction for building differential categories useful to model resource sensitive calculi, and we apply it to categories of games. In one instance, we recover a category previously used to give a fully abstract model of a nondeterministic imperative language. The construction exposes the differential structure already present in this model. A second instance corresponds to a new Cartesian differential category of games. We give a model of a Resource PCF in this category and show that it enjoys the finite definability property. Comparison with a relational semantics reveals that the latter also possesses this property and is fully abstract.",
author = "Jim Laird and Giulio Manzonetto and Guy McCusker",
year = "2011",
doi = "10.1007/978-3-642-22012-8_14",
language = "English",
isbn = "9783642220111",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "186--197",
editor = "Luca Aceto and Monika Henzinger and Jiri Sgall",
booktitle = "Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings",

}

TY - CHAP

T1 - Constructing differential categories and deconstructing categories of games

AU - Laird,Jim

AU - Manzonetto,Giulio

AU - McCusker,Guy

PY - 2011

Y1 - 2011

N2 - We present an abstract construction for building differential categories useful to model resource sensitive calculi, and we apply it to categories of games. In one instance, we recover a category previously used to give a fully abstract model of a nondeterministic imperative language. The construction exposes the differential structure already present in this model. A second instance corresponds to a new Cartesian differential category of games. We give a model of a Resource PCF in this category and show that it enjoys the finite definability property. Comparison with a relational semantics reveals that the latter also possesses this property and is fully abstract.

AB - We present an abstract construction for building differential categories useful to model resource sensitive calculi, and we apply it to categories of games. In one instance, we recover a category previously used to give a fully abstract model of a nondeterministic imperative language. The construction exposes the differential structure already present in this model. A second instance corresponds to a new Cartesian differential category of games. We give a model of a Resource PCF in this category and show that it enjoys the finite definability property. Comparison with a relational semantics reveals that the latter also possesses this property and is fully abstract.

UR - http://dx.doi.org/10.1007/978-3-642-22012-8_14

U2 - 10.1007/978-3-642-22012-8_14

DO - 10.1007/978-3-642-22012-8_14

M3 - Chapter

SN - 9783642220111

T3 - Lecture Notes in Computer Science

SP - 186

EP - 197

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

PB - Springer

CY - Heidelberg, Germany

ER -