Midlands Graduate School Christmas Seminars 2012

The University of Nottingham, Jubilee Campus, Tuesday 18 December, 2012

Information and Programme


The Event

In addition to its yearly programme of taught courses on the mathematical foundations of computing, the Midlands Graduate School (MGS) holds an afternoon of Christmas Seminars. The seminars are free and open to everyone.

The 2012 seminars will take place 14:00–17:30, 18 December, A25 Business School South, at the University of Nottingham Jubilee Campus. Directions for getting to Jubilee Campus can be found here. Business School South is building 7 on the Jubilee Campus map available off the same page. (A25 is actually located in the auditorium building, number 8.)

Coffee will be served, so, for catering purposes, please let the organiser, Henrik Nilsson, know if you intend to come by sending him an e-mail as soon as possible, preferably before 7 December. Additionally, we plan to go for dinner afterwards. Likely Indian or Chinese, depending on logistical factors. As it is close to Christmas, restaurants tend to be busy with Christmas parties. Thus, it is advisable to book ahead. So, if you would like to join for dinner afterwards, again let the organiser know by e-mail, preferably before 7 December, or it might not be possible to accommodate you.


Tuesday, 18 December

14:00--15.00: Session I
14:00 Welcome
Henrik Nilsson, University of Nottingham
14.05 Universal Properties of Impure Programming Languages
Sam Staton, University of Cambridge Computer Laboratory


15:30--17:30: Session II
15:30 How to Analyse Evolutionary Algorithms
Dirk Sudholt, University of Sheffield
16:30 From Type Isomorphisms to Solitaire-like Games
Roland Backhouse, University of Nottingham

18:30Dinner, Kayal

Talk Details

Universal Properties of Impure Programming Languages

Speaker: Sam Staton, University of Cambridge Computer Laboratory
(Joint work with Paul Levy)

Abstract: I will present joint work with Paul Levy on a foundation for impure programming languages. I will explain how the equational theory of LET-VAL in Standard ML can be seen as a non-commutative variant of Lambek's multicategories. Using this structure I will demonstrate that type constructions for impure languages — products, sums and functions — can be characterized by universal properties, just as they can in the pure setting. Our analysis gives a canonical status to earlier abstract ideas, such as Moggi's monads, and puts them on a more syntactic level.

How to Analyse Evolutionary Algorithms

Speaker: Dirk Sudholt, University of Sheffield

Abstract: Evolutionary algorithms mimic the natural evolution of species to "evolve" good solutions for optimisation and design problems, using operators like mutation, crossover, and selection. These popular search heuristics have found wide-spread applications in many domains. Yet the reason behind their success is often elusive, and it is not well understood when these algorithms perform well and when not.

In the last 15 years the area of runtime analysis has emerged, using rigorous mathematical methods for analysing the expected time until an evolutionary algorithm finds a satisfactory solution for a given problem. I will give an introduction into this area, showing how simple evolutionary algorithms can be analysed. A particular focus will be on the role of the crossover operator, and how it can improve performance.

From Type Isomorphisms to Solitaire-like Games

Speaker: Roland Backhouse, University of Nottingham
(Joint work with Wei Chen and Joao Ferreira)

Abstract: Seven trees are one is a well-known type isomorphism due to F.W.Lawvere. It led to the development by Marcelo Fiore (and others) of a beautiful algebraic theory of type isomorphisms based on the notion of a rig. However, although Fiore added a few more, the seven-trees isomorphism has remained a relatively isolated example of intriguing type isomorphisms.

In an attempt to gain a better understanding, we posed ourselves the following problem: Given a number n when is it possible to construct a type T such that n Ts are one? This problem was solved by Wei Chen using the theory of cyclotomic polynomials and reported in his PhD thesis (2012). As a result, we are now able to generate instances of such type isomorphisms ad nauseum.

The seven-trees example was formulated by Dan Piponi as a simple solitaire-like game with checkers played on a one-dimensional tape – a Turing tape. This gave us the idea of using our understanding to formulate an infinite collection of solitaire-like games. Since 2012 is the 100th anniversary of Alan Turing's birth, we thought that a competition based on these “Turing-Tape Games” would be an appropriate way for us to contribute to the celebration of Turing's legacy.

This talk is about our journey from seven-trees-in-one to the Turing-Tape Games competition. We will also explain something of our goals and the failures and successes of the competition.


For dinner, we are we're heading to the South Indian restaurant Kayal, the Nottingham branch:

8, Broad Street
Ph: 0115 9414733
Dinner starts at 18:30!

Last updated 18 December 2012.