BCS-FACS Evening Seminar Series

Games, Interaction and Computation

Professor Samson Abramsky

Oxford University

5 November 2007

5.45pm

The London Mathematical Society

De Morgan House
57-58 Russell Square
London WC1B 4HS

[

[ Presentation slides | Seminar Programme | Location of Venue | Registration ]

Our current understanding of computation has widened enormously beyond the original `closed world' picture of numerical calculation in isolation from the environment. In the age of the Internet and the Web, and now of pervasive and ubiquitous computing, we see that *interaction* and *information flow* between multiple *agents* are essential features of computation. This has required the development of novel mathematical models of interactive computation. One of the compelling ideas which has taken root is to view programs as *strategies* for playing a `game of interaction' with an environment or context. This has led to a substantial development of Game Semantics over the past 15 years, and some striking results, notably the first `fully abstract' models for a range of increasingly sophisticated programming languages. The subject is rich both mathematically and computationally. From the mathematical point of view, there are new categories of game and strategies, with strikingly novel properties, which yield new insights e.g. into the constructions of free models of various important theories. Computationally, the ideas of Game Semantics have been developed in an algorithmic direction, yielding new approaches to compositional model-checking and analysis for programs with state, concurrency, probability and other features. In this seminar we will provide an introduction to and overview of these developments, emphasizing the key concepts and intuitions rather than the technical details. Refreshments will be served from 5.15pm The seminar is free of charge and open to everyone. If you would like to attend, please email Paul Boca by 1 November 2007.