This page is  last updated on the 11th of April 2008

ScopeInvited SpeakersProgrammeLocation; AccommodationRegistrationOrganisationSponsors

BCTCS 2008

24th British Colloquium for
Theoretical Computer Science

7-10 April 2008

Durham University


The 24th British Colloquium for Theoretical Computer Science (BCTCS) was held at Durham University from 7th until 10th April 2008. 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.

Invited Speakers

Martin Abadi (University of California at Santa Cruz and Microsoft Research)
José Félix Costa (Technical University of Lisbon)
Artur Czumaj (University of Warwick)
Martin Henson (University of Essex)
Leonid Libkin (University of Edinburgh)
Rolf Niedermeier (University of Jena)
Gerhard Woeginger (Eindhoven University of Technology) (LMS Keynote speaker)


The programme consisted of nearly 3 days worth of invited and contributed talks, beginning late afternoon on 7th April with registration, coffee and the first invited lecture (at 5pm) and concluding with lunch on 10th April 2008. The abstracts of the talks will be published in the Bulletin of the European Association for Theoretical Computer Science (EATCS). Here is the programme of the invited and contributed talks. The abstracts are linked to the titles of the talks as pdf-files. The Monday lecture took place in the Applebey Theatre in the Department of Geography (five minutes walk from Grey College). All other lectures were in Grey College: the invited lectures as well as the contributed talks in the left colum were in the Holgate Main Conference Room; the others were in the Old Library.

NEW: photos.

Monday 7 April

17.00 - 18.00: Physics and Computation: An Essay on the Unity of Science through Computability (invited talk)        Applebey Lecture Theatre
José Félix Costa

18.15 - 19.15: Reception in Grey College

19.15: Dinner in Grey College

Tuesday 8 April

08.00 - 08.45: Breakfast
09.00 - 10.00: Trends in Parameterized Algorithmics (invited talk)  
Rolf Niedermeier

10.00 - 10.30: On the Complexity of Parity Games 
Faron Moller
Automata on Gauss Words
Rafiq Saleh
10.30 - 11.00: Coffee
11.00 - 11.30: On the Expressive Power of Graph Logic
Timos Antonopoulos
Complete Constraint Satisfaction Problems
András Z. Salamon
11.30 - 12.00: Open Euclidean Relations and Decidable Fragments of the True Existential Theory of the Rational Number Field
Grant Olney Passmore
Valued Constraints - Modelling, Expressive Power and Algebraic Properties
Stanislav Zivný
12.00 - 12.30: Animating Inductive Definitions with Binders
Matthew Lakin
Winning Regions of Pushdown Parity Games: A Saturation Method
Matthew Hague
13.00 - 14.00: Lunch
14.00 - 15.00: Varieties of Schema Calculus (invited talk)
Martin Henson

15.00 - 15.30: Coffee
15.30 - 16.00: Theory and Application of Testing from CSP-CASL
Temesghen Kahsai
On Reasoning about Effects: Seeing the Wood through the Trees
Diana Fulger
16.00 - 16.30: Algorithmic Proof Generation for CSP-CASL-Prover
Liam O'Reilly
Recursive Stochastic Games with Positive Rewards
Dominik Wojtczak
16.30 - 17.00: Safe Reasoning with Logic LTS
Gerald Luettgen
A Concrete Presentation of Game Semantics
William Blum
17.00 - 17.30: A Relative Timed Semantics for BPMN
Peter Y. H. Wong
A Routing Calculus for Distributed Computing
Manish Gaur
19.00: Conference Dinner at Durham Castle

Wednesday 9 April

08.00 - 08.45: Breakfast
09.00 - 10.00: Three Assignment Problems and One Theorem (LMS Keynote speaker)
Gerhard J. Woeginger

10.00 - 10.30: Services Sciences Management and Engineering (SSME) - a Theoretical Computer Science Perspective
Chris Tofts
A Local Move Set for Protein Folding in Triangular Lattice Models
A. Dayem Ullah
10.30 - 11.00: Coffee
11.00 - 11.30: Reasoning about Cryptographic Protection with Spygraphs
Clive Blackwell
New Results on the Complexity of Regular Subgraph Editing Problems
Luke Mathieson
11.30 - 12.30: Towards Correct Programming with Transactional Memory (invited talk)
Martín Abadi

13.00 - 14.00: Lunch
14.00 - 15.00: Databases Meet Verification; or Nested Words and XML Documents (invited tutorial)
Leonid Libkin

15.00 - 15.30: Coffee
15.30 - 16.00: Translucent Abstraction of Algebraic Datatypes with Safe Views
Meng Wang
Size versus Stability in the Marriage Problem
David Manlove
16.00 - 16.30: The Expression Lemma
Ondrej Rypacek
Variations in Weighted Voting Games
Haris Aziz
16.30 - 17.00: Equivalences for Hybrid Systems
Vashti Galpin
One-to-Many Node-Disjoint Paths in (n,k)-Star Graphs
Yonghong Xiang
17.00 - 17.30: Time- and Space-Efficient Periodic Exploration of Undirected Graphs
Ioannis Lignos
Formal Verification of Safety Properties in Systems Defined in Ladder Logic
Karim Kanso
17.30: BCTCS Annual General Meeting
19.00: Dinner

Thursday 10 April

08.00 - 08.45: Breakfast
09.00 - 10.00: Sublinear-time Algorithms (invited tutorial)
Artur Czumaj

10.00 - 10.30: Mobility Challenges in Online Application Development
Divina A. Melomey
Path Coupling without Contraction
Magnus Bordewich
10.30 - 11.00: Coffee
11.00 - 11.30: cALC: Towards Constructive DL for Abstraction and Refinement
Stephan Scheele
Hyperbolic Monoids
Richard M. Thomas
11.30 - 12.00: Algebraic and Relational Semantics for Distributive Substructural Logic
Tomoyuki Suzuki
Verification of Architectural Refactoring Steps by Rule Extraction
Dénes Bisztray
12.00 - 12.30: Independent Typing Rules for Basic Programming Constructs
Mark New
A New Characterization of P6-free Graphs
Pim van 't Hof
12.30: Lunch


The colloquium was held in Grey College at Durham University. 

Directions on how to get there can be found here.

Accommodation and Venue

Accommodation was also in Grey College, in en-suite rooms.


Registration at the colloquium started at 2pm on Monday 7th April in the Reception area of Grey College.
Upon registration delegates received a conference pack including a programme and abstract booklet.

The registration for participation and submitting abstracts has closed.
Participants (particularly PhD students) are encouraged to submit titles and abstracts for contributed talks.
Please download this LaTeX template to produce your abstract, and then email the LaTeX file as an attachment to
If you have a problem using LaTeX you can alternatively send an abstract in plain text to the above e-mail address of the colloquium.
The deadline for registration and submitting abstracts is Sunday 9th March 2008 24:00 GMT.

Please register using the registration page after reading the booking details. Please indicate so if you are already a member of EATCS.
The registration fee of £340 includes three nights en-suite accommodation, all meals and refreshments throughout the day, the
conference banquet in Durham Castle, and one year membership of EATCS.
A day rate of £215 is applicable to those not requiring accommodation.

We supported 38 free places for UK-based PhD students on a first-come first-served basis.
The support covered the registration fee with a maximum of £340, but did not include travel costs.


The colloquium was organised by  Hajo Broersma, Tom Friedetzky and Daniel Paulusma.


We gratefully acknowledge the financial support from EPSRC and the LMS.