Constructing differential categories and deconstructing categories of games

Jim Laird; Giulio Manzonetto; Guy McCusker

doi:10.1007/978-3-642-22012-8_14

Constructing differential categories and deconstructing categories of games

Jim Laird, Giulio Manzonetto, Guy McCusker

Research output: Chapter or section in a book/report/conference proceeding › Chapter or section

5 Citations (SciVal)

160 Downloads (Pure)

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.

Original language	English
Title of host publication	Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Editors	Luca Aceto, Monika Henzinger, Jiri Sgall
Place of Publication	Heidelberg, Germany
Publisher	Springer
Pages	186-197
Number of pages	12
ISBN (Print)	9783642220111
DOIs	https://doi.org/10.1007/978-3-642-22012-8_14
Publication status	Published - 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	6756

Access to Document

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

diff.pdf
The original publication is available at www.springerlink.com
Accepted author manuscript, 346 KB

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). Springer. https://doi.org/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 or section in a book/report/conference proceeding › Chapter or section

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. https://doi.org/10.1007/978-3-642-22012-8_14

@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 or section

SN - 9783642220111

T3 - Lecture Notes in Computer Science

SP - 186

EP - 197

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

A2 - Aceto, Luca

A2 - Henzinger, Monika

A2 - Sgall, Jiri

PB - Springer

CY - Heidelberg, Germany

ER -

Constructing differential categories and deconstructing categories of games

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Semantic Structures for Higher-Order Information Flow

Cite this

Constructing differential categories and deconstructing categories of games

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Projects

Semantic Structures for Higher-Order Information Flow

Cite this