Last updated on 10th August 2005

Poster; Pictures; Scope; Participants; Programme; Abstracts/Slides; Location; Accomodation; Registration; Sponsors; Organisation

21st British Colloquium for Theoretical Computer Science

BCTCS 2005

22-24 March 2005
University of Nottingham, UK

A report on BCTCS 2005 appears in the Bulletin of the European
Association for Theoretical Computer Science, number 86, pages 241-256, June 2005

Jubilee Campus       Jubilee Campus

The 21st British Colloquium for Theoretical Computer Science (BCTCS) will be held at the University of Nottingham from 22nd to 24th March 2005. 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 algorithms, complexity, 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 80 people attended the colloquium:

Natasha Alechina (Nottingham), Thorsten Altenkirch (Nottingham), Alexandra Alecu (Loughborough), Martyn Amos (Exeter), Roland Backhouse (Nottingham), Tony H Bao (Swansea), Ian Bayley (Brookes), Paul Bell (Liverpool), William Blum (Oxford), Russell Boyatt (Warwick), Chris Brown (Kent), Mark Callanan (Kent), James Chapman (Nottingham), Olaf Chitil (Kent), Roy Crole (Leicester), Sharon Curtis (Brookes), Jolie de Miranda (Oxford), Louise Dennis (Nottingham), Aleksandar Dimovsk (Warwick), Attila Egri-Nagy (Hertfordshire), Osama Elhassan (Leicester), Thomas Erlebach (Leicester), Richard Geary (Leicester), Neil Ghani (Leicester), Alan Gibbons (King's), Andy Gimblett (Swansea), Andrew Gordon (Microsoft), Jonathan Grattage (Nottingham), Gregory Gutin (Royal Holloway), Will Harwood (Swansea), Hongmei He (Loughborough), Ralf Hinze (Bonn), Michael Hoffmann (Leicester), Catherine Hope (Nottingham), Graham Hutton (Nottingham), Mark Jago (Nottingham), Kenneth Johnson (Swansea), Matthew Johnson (Durham), Michal Konecny (Aston), Oliver Kullmann (Swansea), Alexander Kurz (Leicester), David Manlove (Glasgow), Clare Martin (Brookes), Conor McBride (Nottingham), Matus Mihalak (Leicester), Neil Mitchell (York), Faron Moller (Swansea), Alberto Moraglio (Essex), Peter Morris (Nottingham), Peter Mosses (Swansea), Jonty Needham (Bath), Wasana Ngaogate (Warwick), Henrik Nilsson (Nottingham), Pablo Nogueira (Nottingham), Bruno Oliveira (Oxford), Cristovao Oliveira (Leicester), Graham Oliver (Leicester), Detlef Plump (York), David Pym (Bath/HP Labs), Rajeev Raman (Leicester), Stephan Reiff-Marganiec (Leicester), Fermin Reig (Nottingham), Markus Roggenbach (Swansea), Ana Salagean (Loughborough), Lucy Saunders-Evans (Cambridge), Jan Schwinghammer (Sussex), Nimish Shah, Colin Sng (Glasgow), Sandra Steinert (York), Chang Su (Liverpool), Ondrej Sykora (Loughborough), Rick Thomas (Leicester), Chris Tofts (HP Labs), John Tucker (Swansea), David Turner (Middlesex), Joel Wright (Nottingham), Na Xu (Cambridge), Jeremy Yallop (Edinburgh), Xiaohui Zhang (Liverpool), Paolo Zuliani (Princeton).


The programme consists of two and a half days of invited talks, tutorials, and contributed talks, beginning on the morning of Tuesday 22nd March and concluding at lunch time on Thursday 24th March 2005. 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. Abstracts and slides are available here.

Invited and stream A talks will be held in Lecture Theatre 1 in The Exchange, stream B talks will be held in room A01 of the School of Computer Science, tea/coffee will be taken in the foyer of The Exchange, and all meals will be taken in The Atrium. A detailed map of the Jubilee Campus showing each of these locations is available here.

Monday 21st March

Participants are invited to meet at 6pm onwards in the Rose and Crown pub, which serves food. Starting from Newark Hall on the Jubilee Campus using this map, follow the dashed pedestrian/cycle route to the left-side of the lake down past the playing fields and tennis courts, and the Rose and Crown is located at the text "Derby Road A6200".

Tuesday 22nd March

08.00 - 08.50 : Breakfast
09.00 - 10.00 : Number Systems and Data Structures (invited talk)
Dr Ralf Hinze, University of Bonn (sponosored by EPSRC)
10.00 - 10.30 : Tea/coffee
10.30 - 11.30 : Stream A Stream B
A Theory of Tracing Pure Functional Programs
Olaf Chitil, University of Kent
Pareto Optimality in House Allocation Problems
David Manlove, University of Glasgow
Exploiring Lightweight Implementations of Generics
Bruno Oliveira, University of Oxford
Geometric Interpretation of Crossover
Alberto Moraglio, University of Essex
Finally, a Simple Semantics
Joel Wright, University of Nottingham
The MSO Theory of Level-2 Term Trees is Decidable
Jolie de Miranda, University of Oxford
11.30 - 12.30 : Stream A Stream B
Tool Support for Modular SOS
Peter Mosses, University of Wales Swansea
Groups with a Co-Context Free Word Problem
Rick Thomas, University of Leicester
Event Structure Semantics for Higher Order Process Calculi
Lucy Saunders-Evans, University of Cambridge
Undecidability of the Membership Problem for a
Diagonal Matrix in a Matrix Semigroup

Paul Bell, University Liverpool
Game Semantics and CSP Based Approach for Software Model Checking
Aleksandar Dimovski, University of Warwick
Computational Classes of Monoids
Michael Hoffmann, University of Leicester
12.30 - 13.30 : Lunch
13.30 - 14.30 : Succinctness (invited talk)
Prof Rajeev Raman, University of Leicester
14.30 - 15.30 : Stream A Stream B
Is Constructive Logic Relevant for Computer Science?
Thorsten Altenkirch, University of Nottingham
Graph Programs for Graph Algorithms
Sandra Steinert, University of York
Weak Bisimulation Approximants
Will Harwood, University of Wales Swansea
Computational Completeness of Rule-Based Languages
Detlef Plump, University of York
Modelling and Specification in the Development and
Analysis of Communications Protocols

Russell Boyatt, University of Warwick
The Source Location Problem in Digraphs
Matthew Johnson, University of Durham
15.30 - 16.00 : Tea/coffee
16.00 - 17.00 : Dependently Typed Programming: An Epigram Induction (invited tutorial)
Dr Conor McBride, University of Nottingham
18.00 - 19.00 : Dinner
19.00 - 24.00 : Newark Hall bar will be open

Wednesday 23nd March

08.00 - 08.50 : Breakfast
09.00 - 10.00 : The Soft Machines: Computing with the Code of Life (invited talk)
Prof Alan Gibbons, King's College London, and Dr Martyn Amos, University of Exeter (sponsored by LMS)
10.00 - 10.30 : Tea/coffee
10.30 - 11.30 : Stream A Stream B
Level of Repair Analysis and Minimum Cost Homomorphisms of Graphs
Gregory Gutin, Royal Holloway, University of London
Nondeterministic Quantum Programming
Paolo Zuliani, Princeton University, USA
Network Discovery and Landmarks in Graphs
Thomas Erlebach, University of Leicester
A Compiler for a Functional Quantum Programming Language
Jonathan Grattage, University of Nottingham
Experiments and Optimal Results for Outerplanar Drawings of Graphs
Hongmei He, University of Loughborough
Total Pasta: Static Analysis For Unfailing Pointer Programs
Neil Mitchell, University of York
11.30 - 12.30 : Stream A Stream B
The Gap between Crossing Numbers and Outerplanar Crossing Numbers
Ondrej Sykora, University of Loughborough
A Typed Semantics for Languages with Higher-Order Store and Subtyping
Jan Schwinghammer, University of Sussex
Automatic Presentations and Classes of Semigroups
Graham Oliver, University of Leicester
Accurate Step Counting
Catherine Hope, University of Nottingham
Algebraic Decompositions of Finite Automata and
Formal Models of Understanding

Attila Egri-Nagy, University of Hertfordshire
Generic Programming in a Dependently Typed Language
Peter Morris, University of Nottingham
12.30 - 13.30 : Lunch
13.30 - 14.30 : Games for Algorithmic Problem Solving (invited tutorial)
Prof Roland Backhouse, University of Nottingham
14.30 - 15.30 : Stream A Stream B
On the Computation of the Linear Complexity and the k-error
Linear Complexity of Binary Sequences With Period a Power of Two

Ana Salagean, University of Loughborough
Markus Roggenbach, University of Wales Swansea
Routing via Single-Source and Multiple-Source Queries in
Static Sensor Networks

Chang Su, University of Liverpool
Parsing and Static Analysis of CSP-CASL
Andy Gimblett, University of Wales Swansea
Joint Base Station Scheduling
Matus Mihalak, University of Leicester
Belief Revision for Resource Bounded Agents
Mark Jago, University of Nottingham
15.30 - 16.00 : Tea/coffee
16.00 - 17.00 : Stream A Stream B
Extensible Knowledge Space
Wasana Ngaogate, University of Warwick
Combinatorial Tools for Propositional Satisfiability Decision
Oliver Kullmann, University of Wales Swansea
A Framework Based on Coordination and Software
Architecture for Mobile Systems

Cristovao Oliveira, University of Leicester
Foundations of a Generic C++ Library for Generalised Satisfiability Problems
Tony H Bao, University of Wales Swansea
Architectural Support for Collaboration Technology for
Socio-Technical Systems

Osama Elhassan, University of Leicester
New Solution for Multiple Mobile Agent Rendezvous in a Ring
Xiaohui Zhang, University of Liverpool
17.00 - 17.30 : Annual General Meeting
18.30 - 20.00 : Colloquium Dinner
20.00 - 01.00 : Newark Hall bar will be open

Thursday 24th March

08.00 - 08.50 : Breakfast
09.00 - 10.00 : Samoa: Formal Tools for Securing Web Services (invited talk)
Dr Andrew Gordon, Microsoft Research, Cambridge
10.00 - 10.30 : Tea/coffee
10.30 - 11.30 : Logics for Transition Systems from Representations of Functors
Alexander Kurz, University of Leicester
Type-safe Clipboard Operations for Document-Centred Functional Programs
Mark Callanan, University of Kent
Checking Dependently Typed Programs
James Chapman, University of Nottingham
11.30 - 12.10 : Coherence via Confluence
Neil Ghani, University of Leicester
Termination Analysis of Lambda-Calculus and a Subset of Core ML
William Blum, University of Oxford


The colloquium will be held on the Jubilee Campus of the University of Nottingham, which has won many awards for its design and environmental features.

Nottingham is centrally located in the UK, and is easily reachable by all forms of transport.

By car: Leave the M1 motorway at junction 25 or 26, and follow the route to the Jubilee Campus using this map. Enter the campus itself via the main entrance on Wollaton Road on this map, as the other entrance (on Triumph Road) is only accessible with an electronic pass. Tell the security staff at the main entrance that you are attending the BCTCS conference, and they will direct you to the free visitors car park nearby. Make sure not to park elsewhere, as all other spaces require a parking permit and are subject to stickering or clamping.

By train or bus: The Jubilee Campus is around 10 minutes by taxi from the train and bus stations in Nottingham city centre. Online timetables and booking are available for both trains and buses.

By plane: The campus is around 30 minutes by taxi from Nottingham East Midlands airport, which has direct scheduled flights to many European destinations. Those without a direct flight should be able to make the journey with a single change, or may prefer to fly to Birmingham, Manchester, or Heathrow airports and then take the train to Nottingham. If you will be flying to Nottingham please book your ticket as soon as possible, as most of the carriers are budget airlines whose cheap flights are very popular. Online timetables and booking are available for most flights, via the above links.

In case you require a taxi as part of your return journey, here are some local numbers:

Central Taxi: 0115 975 2222
DG Taxi: 0115 960 7607
County Taxi: 0115 942 5425


Full registration includes single en-suite accomodation in Newark Hall on the Jubilee Campus for the nights of Monday 21st, Tuesday 22nd and Wednesday 23rd March. Rooms are available from 3pm on the day of arrival, and must be vacated by 10am on the day of departure. Keys can be obtained from the porter at the entrance of Newark Hall. A detailed map of the Jubilee Campus is available here.


Registration is now closed.


EPSRC logo

LMS logo


The colloquium is organised by Graham Hutton. All enquiries should be addressed to:

email address