Informatics Report Series


Report   

EDI-INF-RR-0759


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Nominal Games and Full Abstraction for the Nu-Calculus
Authors: Samson Abramsky ; Dan Ghica ; Andrzej Murawski ; Luke Ong ; Ian Stark
Date:Jul 2004
Publication Title:Proceedings of LICS 2004 (IEEE Symposium on Logic in Computer Science)
Publisher:IEEE Computer Society
Publication Type:Conference Paper Publication Status:Published
Page Nos:150-159
DOI:10.1109/LICS.2004.1319609
Abstract:
We introduce nominal games for modelling programming languages with dynamically generated local names, as exemplified by Pitts and Stark's nu-calculus. Inspired by Pitts and Gabbay's recent work on nominal sets, we construct arenas and strategies in the world (or topos) of Fraenkel-Mostowski sets (or simply FM-sets). We fix an infinite set N of names to be the "atoms" of the FM-theory, and interpret the type ν of names as the flat arena whose move-set is N. This approach leads to a clean and precise treatment of fresh names and standard game constructions (such as plays, views, innocent strategies, etc.) that are considered invariant under renaming. The main result is the construction of the first fully-abstract model for the nu-calculus.
Copyright:
IEEE 2004
Links To Paper
Page by author
Page by publisher
Bibtex format
@InProceedings{EDI-INF-RR-0759,
author = { Samson Abramsky and Dan Ghica and Andrzej Murawski and Luke Ong and Ian Stark },
title = {Nominal Games and Full Abstraction for the Nu-Calculus},
book title = {Proceedings of LICS 2004 (IEEE Symposium on Logic in Computer Science)},
publisher = {IEEE Computer Society},
year = 2004,
month = {Jul},
pages = {150-159},
doi = {10.1109/LICS.2004.1319609},
url = {http://www.inf.ed.ac.uk/~stark/nominalgames.html},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh