25th Estonian Winter School in Computer Science (EWSCS)
XXV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2020

Andrew M. Pitts

Department of Computer Science & Technology
University of Cambridge
United Kingdom

An introduction to nominal sets


Nominal sets provide a mathematical foundation for a large body of work motivated by an important question in computer science to do with constructs involving names: when is a mathematical structure used to model some form of computation dependent upon, or independent from, some given names? The theory is based on some simple, but subtle ideas to do with permutations of names and the notion of "finitely supported" mathematical structures, which first arose in mathematical logic in the 1930s. About 20 years ago the lecturer and Jamie Gabbay showed that this can provide a mathematical theory and an accompanying logic for some of the key concepts to do with representing and computing with data involving bound names, such as freshness, abstraction and scoping of names (for which work they were given the Alonzo Church Award in 2019). Since then the theory has been generalised and applied, becoming a fundamental tool for understanding locality in models of computation and programming languages. It has applications to the syntax and semantics of programming languages, to logics for machine-assisted reasoning about programming-language semantics, to the automatic verification of specifications in process calculi and to automata theory over infinite alphabets, with applications to querying XML and databases.

The lectures will introduce the theory of nominal sets and survey some of its applications, particularly in the realm of functional programming.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed April 10, 2020 22:30 Europe/Helsinki (GMT +03:00) by local organizers, ewscs20(at)cs.ioc.ee
EWSCS'20 page: //cs.ioc.ee/ewscs/2020/