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.

Scope

Participants

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).

Programme

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
17.00- 17.30:	Coffee
17.30- 18.30:	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
18.30- 20.30:	Buffet
Wednesday 5th April
07.45- 08.45:	Breakfast
09.00- 10.00:	Unifying theories of concurrency (Keynote Lecture) Tony Hoare, Microsoft Research Cambridge
10.00- 10.30:	Coffee
10.30- 11.30:	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
11.30- 12.30:	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
12.30- 13.30:	Lunch
13.30- 14.30:	A Tutorial on Efficient Sampling (Keynote Lecture) Mark Jerrum, Edinburgh University
14.30- 15.30:	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
15.30- 16.00:	Coffee
16.00- 17.20:	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
	Overhang Mike Paterson, Warwick University	Future Trends in Hypercomputation Mike Stannett, Sheffield University
17.45& 18.10:	Bus to Museum
20.00- 22.30:	Dinner at Museum
22.30& 22.45:	Bus to Campus
Thursday 6th April
07.45- 08.45:	Breakfast
09.00- 10.00:	Toughness in graphs: structural and algorithmic aspects (LMS Keynote Lecture in Discrete Mathematics) Hajo Broersma, Durham University
10.00- 10.30:	Coffee
10.30- 11.30:	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
11.30- 12.30:	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
12.30- 13.30:	Lunch
13.30- 14.30:	Alternation as an algorithmic construct (EPSRC-sponsored Keynote Lecture) Moshe Vardi, Rice University
14.30- 15.30:	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
15.30- 16.00:	Coffee
16.00- 17.20:	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
17.20- 17.30:	Refreshments
17.30- 18.45:	Annual General Meeting (including a presentation by Samson Abramsky on the formation of a Learned Society for Computer Science)
19.30- 22.00:	Dinner
Friday 7th April
07.45- 08.45:	Breakfast
09.00- 10.00:	A Tutorial on Proof Complexity (EPSRC-sponsored Keynote Lecture) Stephen Cook, Toronto University
10.00- 10.30:	Coffee
10.30- 11.30:	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
11.30- 12.30:	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
12.30- 13.30:	Lunch

Contributed talks:

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

Location

Directions on how to get there can be found here.

Swansea	University	Campus

Accommodation and Venue

Registration and Student Grants

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.

Sponsors

Organisation

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