BCTCS 2014 – British Colloquium for Theoretical Computer Science

We are delighted to announce invited talks from:

Leszek A. Gąsieniec, University of Liverpool

Title: Distributed Maintenance of Mobile Entities

Abstract: With the recent advent of ad-hoc, not well-structured, large,
and (very often) dynamic network environments there is a strong
need for more robust, universal, and inexpensive distributed
network protocols. The purpose of these protocols is to support
basic network formation and integrity mechanisms as well as more
dedicated tasks such as information dissemination, network search
and exploration, network monitoring and others.

One of the novel and promising alternatives in supporting such
network protocols are dedicated teams of mobile entities (MEs) that
can work independently on top of basic network system routines.
The MEs’ ability to communicate and to move within the environment
impels the design and implementation of efficient formation,
communication and navigation mechanisms including motion control
and coordination mechanisms that allow MEs to perform
dedicated tasks collectively.

We will provide an introduction to the field and will discuss several
extensively studied algorithmic problems as well as those just touched
upon in the recent years. The talk will be concluded with open problems.

Achim Jung, University of Birmingham

Title: A modal Belnap logic

Abstract: Four valued logic was introduced by Nuel Belnap in the 70s.
It is very easy to motivate and seems to be central to Computer
Science; in fact, one of his papers on the subject was called “How a
computer should think”. Adding mathematical structure to his basic
ideas turned out not to be so easy, however. Much work was done by
Arieli and Avron in the 90s, and more recently, by Umberto Rivieccio,
a collaborator on the work to be presented, which concerns a modal
extension of Belnap’s work. The topic is also related to my
longstanding interest in using Stone Duality to link semantics and
logic for computer science.

Timo Kötzing, Friedrich-Schiller-Universität, Jena

Title: Recent Advances in Inductive Inference

Abstract: 3,5,7,11,13 — what’s next? What general rule (apparently) produces this sequence? Maybe the sequence lists all the odd primes, but what if the next datum is 15? Maybe all odd numbers that are not squares? Since the 1960’s there are formal models defining what it means to learn or predict such sequences; this area of research is called inductive inference. In this talk I will briefly review the main classical results and then focus on recent advances in inductive inference, especially concerning the development of general techniques. Applications of these techniques include, for example, questions regarding avoidance of seemingly inefficient learning behavior.

Jeffrey Shallit, University of Waterloo, the LMS-sponsored Keynote Speaker in Discrete Mathematics

Title: Open Problems in Automata Theory

Abstract: In this talk I will survey some of my favorite open problems from automata theory, including the separating words problem, decidability problems related to number theory and the Endrullis-Hendriks problem on transducers.