Last updated on the 28th March 2006

Poster; Scope; Participants; Programme; Location; Accommodation; Registration and Student Grants; Sponsors; Organisation; Gallerie; Gallerie (BW); Report

BCTCS 2006

22nd British Colloquium for
Theoretical Computer Science

4-7 April 2006

Swansea University


The 22nd British Colloquium for Theoretical Computer Science (BCTCS) will be held at Swansea University from 4th to 7th April 2006. The purpose of BCTCS is to provide a forum in which researchers in theoretical computer science can meet, present research findings, and discuss developments in the field. It also aims to provide an environment in which PhD students can gain experience in presenting their work, and benefit from contact with established researchers.


The scope of the colloquium includes all aspects of theoretical computer science, including automata theory, algorithms, complexity theory, semantics, formal methods, concurrency, types, languages and logics. Both computer scientists and mathematicians are welcome to attend, as are participants from outside of the UK.


The following 122 people registered for the colloquium:

Samson Abramsky (Oxford University), Andreas Albrecht (Hertfordshire University), Thorsten Altenkirch (Nottingham University), Haris Azis (Warwick University), Ioannis Baltopoulos (Cambridge University), Jean Baillie (Hertfordshire University), Joachim Baran (Manchester University), Arnold Beckmann (Swansea University), Mihalis Beis (Liverpool University), Ulrich Berger (Swansea University), Graham Birtwistle (Sheffield University), Jens Blanck (Swansea University), Julian Bradfield (Edinburgh University), Hajo Broersma (Durham University), Nick Cameron (Imperial College), Luis Cereceda (London School of Economics), Aziem Chawdhary (Queen Mary, University of London), Chi Ming Chuang (Swansea University), Stephen Cook (Toronto University), Páidí Creed (Edinburgh University), David Cunningham (Imperial College), Sharon Curtis (Oxford Brookes University), Neil Datta (Imperial College), Aleksandar Dimovski (Warwick University), Michael Dodds (York University), Alastair Donaldson (Glasgow University), Jan Duracz (Aston University), Martin Dyer (Leeds University), Edith Elkind (Warwick University), Simon Foster (Sheffield University), Alan Gibbons (King's College London), Andy Gimblett (Swansea University), Leslie Goldberg (Warwick University), Stephen Gorton (Leicester University), Alexey Gotsman (Cambridge University), Phil Grant (Swansea University), Jonathan Grattage (Nottingham University), Alexander Green (Nottingham University), Aled Griffiths (Manchester University), Neal Harman (Swansea University), Will Harwood (Swansea University), Abubakar Hassan (King's College London), Matthew Henderson (Swansea University), Michaela Heyer (University College Cork), Roger Hindley (Swansea University), Tony Hoare (Microsoft Cambridge), Catherine Hope (Nottingham University), Tie Hou (Swansea University), Liyang Hu (Nottingham University), Wan Huang (London School of Economics), Andrew Hughes (Sheffield University), Akbar Hussain (Queen Mary, University of London), Graham Hutton (Nottingham University), Rob Irving (Glasgow University), Markus Jalsenius (Warwick University), Mauro Jaskelioff (Nottingham University), Mark Jerrum (Edinburgh University), Jan Johannsen (LMU Munich), Kenneth Johnson (Swansea University), Savas Konur (Manchester University), Oliver Kullmann (Swansea University), Ranko Lazic (Warwick University), Cindy Li (Liverpool University), Li Li (Swansea University), Olga Lightfoot (Queen Mary, University of London), Gerald Luettgen (York University), Tiejun Ma (Edinburgh University), David Manlove (Glasgow University), Erik Arne Mathiesen (Queen Mary, University of London), Steve Matthews (Warwick University), Andrew McGrae (Liverpool University), Markus Michelbrink (Swansea University), Neil Mitchell (York University), Matthias Mnich (London School of Economics), Faron Moller (Swansea University), Peter Morris (Nottingham University), Peter Mosses (Swansea University), Dimitrios Mostrous (Imperial College), Jonty Needham (Bath University), Gregg O'Malley (Glasgow University), Nick Palmer (Warwick University), Nick Papanikolaou (Warwick University), Daniel Paulusma (Durham University), Mike Paterson (Warwick University), Kasper Pedersen (Warwick University), Doron Peled (Warwick University), Alexis Petrounias (Imperial College), Pattarawit Polpinit (Warwick University), David Pym (HP Labs Bristol), Stephan Reiff-Marganiec (Leicester University), Robert Reitmeier (Nottingham University), Bilel Remmache (Southampton University), Mark Rhodes (Durham University), Markus Roggenbach (Swansea University), Ondrej Rypacek (Nottingham University), Sam Sanjabi (Oxford University), Paul Sant (University of Luton), Rahul Savani (London School of Economics), Monika Seisenberger (Swansea University), Anton Setzer (Swansea University), Nikolaos Siafakas (King's College London), Alexandros Skaliotis (King's College London), Gareth Smith (Imperial College), Colin Sng (Glasgow University), Mike Stannett (Sheffield University), Roger Stein (Swansea University), Kathleen Steinhofel (King's College London), Iain Stewart (Durham University), Wouter Swierstra (Nottingham University), Abhishek Thakur (Queen Mary, University of London), Rick Thomas (Leicester University), Chris Tofts (HP Labs Bristol), Ashutosh Trivedi (Warwick University), John Tucker (Swansea University), David Turner (Middlesex University), Moshe Vardi (Rice University), Zheng Wang (Manchester University), Dominic Wojtczak (Edinburgh University), Taoyang Wu (Queen Mary, University of London), Yonghong Xiang (Durham University), Hong Qing Yu (Leicester University), Michele Zito (Liverpool University).


The programme will begin with Peter Mosses' Keynote Lecture at 5:30pm on Tuesday 4 April, preceded by coffee and biscuits at 5:00pm and followed by a light buffet, and consist thereafter of two and a half days of invited and contributed talks, beginning at 9am on Wednesday 5 April and concluding at 12:30pm on Friday 7th April 2006. The proceedings will end with lunch after the final session.

The abstracts of the talks will be published in the Bulletin of the European Association of Theoretical Computer Science (EATCS), as well as on the colloquium web site. Any auxiliary material which is made available by speakers, such as talk slides or a supporting paper, will also be included on the web site. The detailed programme is given below.

Keynote Lectures will be held in the Faraday Lecture Theatre, and contributed talks will be held in two parallel streams, in the Faraday Lecture Theatre and in the nearby Robert Recorde Room. Coffee will be served in the foyer outside the Faraday Lecture Theatre, and all lunches will be taken in Fulton House.

Tuesday 4th April

The Meaning of It All: Programming Language Semantics, From Scott and Strachey to Semantics/Online
(BCS-FACS Keynote Lecture on Formal Methods)
Peter Mosses, Swansea University

Wednesday 5th April

Unifying theories of concurrency
(Keynote Lecture)
Tony Hoare, Microsoft Research Cambridge
Faraday Lecture Theatre Robert Recorde Room
Implementing atomicity with locks
David Cunningham, Imperial College
Graph Transformation in Constant Time
Michael Dodds, York University
Combining Timing, Localities and Migration in a Process Calculus
Andrew Hughes, Sheffield University
Stable Matching Problems with Constant Length Preference Lists
Gregg O'Malley, Glasgow University
Compiling Interaction Nets
Abubakar Hassan, KCL
Popularity in the Capacitated House Allocation Problem
Colin Sng, Glasgow University
Faraday Lecture Theatre Robert Recorde Room
Task-Oriented Business Requirements Elicitation for Web Services
Stephen Gorton, Leicester University
Comparing parallel and sequential Selfish Routing in the Atomic Players setting
Pattarawit Polpinit, Warwick University
A Formal Model for Web-Service Composition
Simon Foster, Sheffield University
Nash Equilibria in Graphical Games on Trees Revisited
Edith Elkind, Warwick University
Model checking business processes
Ioannis Baltopoulos, Cambridge University
Enumerating Nash equilibria for game trees
Wan Huang, LSE
A Tutorial on Efficient Sampling
(Keynote Lecture)
Mark Jerrum, Edinburgh University
Faraday Lecture Theatre Robert Recorde Room
Logarithmic Simulated Annealing for Protein Folding
Alexandros Skaliotis, KCL
QML: A functional quantum programming language
Jonathan Grattage, Nottingham University
A scan Markov chain for sampling colourings
Kasper Pedersen, Warwick University
Session Types for Object-Oriented Languages
Dimitrios Mostrous, Imperial College
Improved mixing bounds for the anti-ferromagnetic Potts model on Z^2
Markus Jalsenius, Warwick University
The Small Chorded Object-Oriented Language
Alexis Petrounias, Imperial College
Faraday Lecture Theatre Robert Recorde Room
The complexity of counting homomorphisms to directed acyclic graphs
Martin Dyer, Leeds University
A Framework for Automated Verification of Quantum Cryptographic Protocols
Nick Papanikolaou, Warwick University
FA-presentable structures
Rick Thomas, Leicester University
Reversible Quantum Circuits from Irreversible functions
Alexander Green, Nottingham University
Mike Paterson, Warwick University
Future Trends in Hypercomputation
Mike Stannett, Sheffield University
Bus to Museum
Dinner at Museum
Bus to Campus

Thursday 6th April

Toughness in graphs: structural and algorithmic aspects
(LMS Keynote Lecture in Discrete Mathematics)
Hajo Broersma, Durham University
Faraday Lecture Theatre Robert Recorde Room
Fixed Point Free Property is NP-complete
Taoyang Wu, Queen Mary, University of London
Average Time Games
Ashutosh Trivedi, Warwick University
Vertex and Edge Covers with Clustering Properties: Complexity and Algorithms
David Manlove, Glasgow University
Computation of Correlated Equilibria in Succinctly-Representable Games
Matthias Mnich, LSE
Fault-tolerant properties of k-ary n-cube
Yonghong Xiang, Durham University
Hard-to-Solve Bimatrix Games
Rahul Savani, LSE
Faraday Lecture Theatre Robert Recorde Room
PAC-Learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance
Nick Palmer, Warwick University
A Fully Abstract Game Semantics for Answer Set Programming
Jonty Needham, Bath University
Combinatorics of colouring 3-regular trees
Paul Sant, Luton University
Full Abstraction For Additive Aspects
Sam Sanjabi, Oxford University
Efficient probe selection in microarray design
Cindy Li, Liverpool University
Game Semantics Supported Component Verification
Aleksander Dimovski, Warwick University
Alternation as an algorithmic construct
(EPSRC-sponsored Keynote Lecture)
Moshe Vardi, Rice University
Faraday Lecture Theatre Robert Recorde Room
On proving liveness properties of programs
Alexey Gotsman, Cambridge University
Multirelational Folds
Sharon Curtis, Oxford Brookes University
LTL with the Freeze Quantifier and Register Automata
Ranko Lazic, Warwick University
CATCH - Case And Termination Check for Haskell
Neil Mitchell, York University
Linear Temporal Logics and Grammars
Joachim Baran, Manchester University
Fusion in Less Space
Catherine Hope, Nottingham University
Faraday Lecture Theatre Robert Recorde Room
General techniques for symmetry reduction in model checking
Alastair Donaldson, Glasgow University
A state abstraction for Java like languages
Nick Cameron, Imperial College
Efficient Model Checking for LTL with Partial Order Snapshots
Doron Peled, Warwick University
Towards Operations on Operational Semantics
Mauro Jaskelioff, Nottingham University
Semantic Web Services Composition via Planning as Model Checking
Hong Qing Yu, Leicester University
Abstract Hoare Logic and dynamical systems
Erik Arne Mathiesen, Queen Mary, University of London
Lower bounds for Dominating Sets in Web Graphs
Michele Zito, Liverpool University
The Theory of Spatial Data Types and Constructive Volume Geometry
Kenneth Johnson, Swansea University
Annual General Meeting
(including a presentation by Samson Abramsky on the formation of a Learned Society for Computer Science)

Friday 7th April

A Tutorial on Proof Complexity
(EPSRC-sponsored Keynote Lecture)
Stephen Cook, Toronto University
Faraday Lecture Theatre Robert Recorde Room
Inductive Recursive Definitions and Generic Programming
Anton Setzer, Swansea University
Locally constrained graph homomorphisms and degree refinement matrices
Daniel Paulusma, Durham University
Real arithmetic test suite for a theorem prover
Olga Lightfoot, Queen Mary, University of London
Isomorphisms for Context-Free Types
Wouter Swierstra, Nottingham University
A Component Model for Verified Software
Zheng Wang, Manchester University
Containing Families
Peter Morris, Nottingham University
Faraday Lecture Theatre Robert Recorde Room
Using (hyper)graph decomposition for satisfiability decision
Oliver Kullmann, Swansea University
Computational Idioms, Symmetry, Reversibility and K-theory
Neil Datta, Imperial College
An intelligent example-generator for graph theory
Michaela Heyer , University College Cork
A fully labeled lambda calculus
Nikolaos Siafakas, KCL
Recolouring Graph Colourings
Luis Cereceda, LSE
Stop thinking about bottoms when writing programs!
Thorsten Altenkirch, Nottingham University

Contributed talks:

A list of the talks offered by participants to date is available here.


The colloquium will be held in the Department of Computer Science at Swansea University. The Department is located in Singleton Park, right on the coast of Swansea Bay; the city is to the east, the North Devon coast is visible to the south, Brecon Beacons National Park is to the north, and the old fishing village of Mumbles is to the west. Mumbles marks the start of the Gower Peninsula, an area of outstanding natural beauty, with long beaches, dramatic coastal scenery, and a rich history.

Directions on how to get there can be found here.

swanuk.jpg (7117 bytes) swanicon.jpg (8893 bytes) campusthumb.gif (6981 bytes)
Swansea University Campus

Accommodation and Venue

Accommodation will be on campus, in en-suite University halls of residence. Residences are equipped with wireless network access and are five minutes walk from the Department of Computer Science and the conference venue.

Registration and Student Grants

Registration is closed.

Participants (particularly PhD students) are encouraged to submit titles and abstracts for contributed talks. The registration fee of £285 includes three nights en-suite accommodation, all meals and refreshments throughout the day, an excursion and banquet at the newly opened National Waterfront Museum, and one year membership of EATCS. A reduced rate of £160 is applicable to those not requiring accommodation.

EPSRC has provided free registration for 48 UK-based PhD students to be allocated on a first-come-first-serve basis, with preference given to students offering to contribute talks.

* * * Note: All student grants have now been allocated. * * *

The deadline for registration is February 20, 2006. Places in accommodation are strictly limited, so timely registration is essential.


UW Swansea logo IT Wales logo
WDA logo LMS logo
EPSRC logo BCS FACS logo


The colloquium is organised by Faron Moller, Markus Roggenbach and Neal Harman.