University of Leicester


BCTCS 19, April 7-9, 2003


The British Colloquium for Theoretical Computer Science (BCTCS) is an annual conference providing a forum for research in all areas of theoretical computer science. As such, it aims to provide an informal setting within which researchers can meet and discuss recent developments and results in the broad swathe of the subject rather than in just their own area of specialty.

The BCTCS is also dedicated to the development and training of postgraduate research students. Indeed, the relaxed nature of the conference provides an excellent environment where postgraduate students may gain the experience of presenting their work to their colleagues and benefit from contact with established researchers in the community. A number of grants are available to fund the accommodation and registration costs of postgraduate students who are willing to give talks.

As one of the largest theoretical computer science groups within the United Kingdom, we are pleased to announce that BCTCS 19 will be held in the Department of Maths and Computer Science at the University of Leicester between April 7-9 2003. We are pleased to have invited talks in the areas of programming language semantics, category theory, algorithms, formal languages and automata theory given by:

  • Professor Achim Jung , University of Birmingham, UK

  • Professor Bill Lawvere , State University of New York, USA
    The boolean algebra classifying topos and the complexity of finite automata

    The outline of the talk is as follows: i) Adequacy of Measurement and Boolean Algebra; ii) Classifying Topos and the Aufhebung of Complexity; iii) Second Order Automata; and iv) Finite Toposes and their Internal Theory

  • Professor Kurt Mehlhorn , Max Planck Institute for Computer Science, Germany
    Certifying Algorithms

  • Dr S Muthukrishnan, Rutgers University, USA
    Data Stream Algorithmics

    Automatic data feeds arising from monitoring applications in telephone network, the Internet, atmospheric and space stations arrive as data streams, i.e., as a series of observations at a very high speed. What are mathematical, algorithmic and engineering ideas we need to manage and analyze such streams? The talk will be an idiosyncratic overview of this applied algorithmic research agenda, with open problems.

  • Professor Jean-Eric Pin, Universite Paris Denis Diderot et CNRS, France
    Logic and Automata

    This is a survey lecture on the connections between formal logic and the theory of automata. The logic we have in mind is the sequential calculus of Buchi, a system which allows to formalize properties of words. In this logic, there is a predicate for each letter and the unique extra non logical predicate is the relation symbol, which is interpreted as the usual order on the integers. Several famous classes have been classified within this logic.

    We shall briefly review the main results concerning second order, which covers classes like PH, NP, P, etc. and then study in more detail the results concerning the monadic second order and the first order logic. In particular, we shall survey the results and fascinating open problems dealing with the first order quantifier hierarchy.

Attendees and other contributed talks can be found here while registration details can be found here

BCTCS 19 will be organised by Neil Ghani, Rajeev Raman and Rick Thomas. Further details can be obtained by emailing

Author: Neil Ghani (
Author: Steve Lakin (
© University of Leicester 13th December 2002. Last modified: 5th August 2003, 11:48:03
Informatics Web Maintainer. Any opinions expressed on this page are those of the author.