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
TBA
-
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 bctcs19@mcs.le.ac.uk
|