Nominal Sets
Lecturer:
Prof. Mikolaj Bojanczyk
(Warsaw University).
About the lecturer | Course Summary | Slides | Assignment
About the lecturer:
Mikolaj Bojanczyk has developed several new paths in automata theory, like
automata operating on abstract data, or asymptotic behaviour of counters.
His work often addresses the issue of decidability of automata-theoretic
questions. He received a number of prestigious prizes, including the
Ackermann awards for PhD dissertation (2005), the Kuratowski award (2007), and
the Presburger award for young scientists (granted by EATCS, 2010).
Course summary: Nominal sets are a different kind of set theory. "Nominal sets" are the computer science name for permutation models of set theory, which were invented by Abraham Fraenkel in the 1920's and further studied by Andrzej Mostowski. Nominal sets were rediscovered for computer science by Gabbay and Pitts in 1999 (and given the name "nominal sets"), as a way of talking about name binding in lambda terms and logical formulas.
This talk is about yet another rediscovery of nominal sets, this time as a way of talking about automata with infinite alphabets. The point in nominal sets is that there is a different notion of finite set. For example, the set of rational numbers is a finite set (of course there is a catch).
Assignment: Tasks are here: [PDF]. Due: 29th February. Please send a pdf to Mikolaj Bojanczyk.