Theoretical computer science amsterdam (TCSA)



Theoretical Computer Science Amsterdam Day "(TCSA Day)"

Faculty of Science


Conference / Symposium

We are happy to invite you to the first
Theoretical Computer Science Amsterdam (TCSA) Day
which will take place on

  Friday October 30, 2009
  Vrije Universiteit
  room A301 in the Faculty of MEDICINE (!)

The programme consists of talks by researchers
from CWI, UvA, and VU. The schedule is as follows;
the abstracts of the talks can be found below.

09:30       coffee

10:00-10:45 Wan Fokkink (VU)
            Analysis of C. elegans Vulval Development using Petri Nets

10:45-11:15 coffee

11:15-11:45 Christian Schaffner (CWI)
            Quantum cryptography

11:45-12:15 Joerg Endrullis (VU)
            Productivity and The Pebbleflow Method

12:15-13:30 lunch (not organised)

13:30-14:15 Jan Bergstra (UvA)
            From Material Division to the off-line Halting Problem

14:15-15.00 Yde Venema (UvA)
            Coalgebra Atomata (towards a Universal Theory of Automata)

15:00-15:30 tea

15:30-16:15 John Hitchcock (University of Wyoming and CWI)
            Density and Complexity of Instances in NP-Complete Sets


There is no need to register. Tea and coffee is
offered; lunch is not organised. Please forward
this announcement also to your PhD- and Master
students !

Please note that the TCSA Day is in the
Faculty of Medicine, so not in the building of the
computer science department of the VU.
How to get there ?
For how to get to the VU, please see the following webpage:
Then the talks are in the Faculty of Medicine
which is building number 6 on the following campus-map:

The TCSA Day is intended to be an annual event,
taking place in the Fall, so that it alternates
with the national NVTI Theory Day that takes
place in Spring. The TCSA Day is organized by
CWI, UvA, and VU together.

The Steering Committee of the TCSA Days consists of
  Jan Bergstra (UvA)
  Wan Fokkink (VU)
  Harry Buhrman (CWI)

The TCSA Day is also announced via the following website:


kind regards,
  the organizers:
  Alban Ponse (
  Femke van Raamsdonk (
  Leen Torenvliet (
  Ronald de Wolf (


Abstracts of the talks of the first TCSA Day on October 30, 2009:
  Wan Fokkink (VU)
  Analysis of C. elegans Vulval Development using Petri Nets

Understanding the processes involved in multi-cellular pattern formation
is a central problem of developmental biology, hopefully leading to many
new insights, e.g., in the treatment of various diseases. Defining
suitable computational techniques for development modelling, able to
perform in silico simulation experiments, is an open and
challenging problem.

I will explain a coarse-grained, quantitative approach based on Petri
nets, to mimic the behaviour of the biological processes during
multicellular differentiation. We have applied this approach to the
well-studied process of C. elegans vulval development. Our model correctly
reproduces a large set of in vivo experiments with statistical accuracy.
It also generates gene expression time series in accordance with recent
biological evidence. Finally, we modelled the role of microRNA mir-61
during vulval development and predict its contribution in stabilising cell
pattern formation.


  Christian Schaffner (CWI)
  Quantum Cryptography

We give a general introduction to quantum cryptography.  Its most
prominent application is Quantum Key Distribution (QKD), a three-party
scenario where two honest parties Alice and Bob use quantum communication
to establish a key which is secure against an all-powerful
eavesdropper Eve.
The second part of the talk is concerned with quantum cryptography among
only two players. In this scenario, it can be shown that security can only
be obtained by imposing additional assumptions. We present recent results
about the possibility of basing two-party cryptography on the natural
assumption that storing large amounts of quantum information is a
formidable technical challenge.


  Joerg Endrullis (VU)
  Productivity and The Pebbleflow Method
We are interested in finite specifications of infinite lists of data,
also called streams, that are based on orthogonal rewrite rules.
A stream specification is called 'productive' if every element of
the stream can be evaluated. In a slogan, one could say that
productivity is for infinite objects what termination is for finite
data specifications.

Although productivity is undecidable in general, for restricted
formats sufficient conditions or even decidability can be established.
For this purpose we model the process of evaluating a stream
specifications by the dataflow of abstract stream elements,
called `pebbles', in finite `pebbleflow nets'.

More information is available at .
This includes an implementation of the decision algorithm
and a animation tool visualizing the data flow in pebbleflow nets.


  Jan Bergstra (UvA)
  From Material Division to the off-line Halting Problem
Material division simplifies algebra by assuming that the inverse of zero is
zero. Mathematicians don't like that and prefer relevant division instead. I
will first survey what we know about material division and what are the main
open issues that require further work. Then I will describe how mathematics
deals with division by zero in terms of RDC, the relevant division
convention. It is argued that in this particular case RDC provides a better
explanation of dealing with problematical function values than the more
well-known notion of a partial function.

These considerations can be transposed to the setting of the instruction
sequence based (off-line) halting problem and its many variations.
Application of a program to an input is specified by an operator 'apply' and
we will discuss how that operator may be first made total and then may be
used under a relevant application convention similar to RDC. It will be
shown as an illustration that the presence of a diagonal argument regarding
off-line halting assessment and the algorithmic unsolvability of that
problem are independent issues. It will also be shown that the off-line
halting for an instruction sequence notation problem may be solvable by an
instruction sequence written in that notation. That is a reflexive
meta-program for halting may be found in some cases. This may be contrasted
with the on-line halting problem (halting forecasting) which cannot be
solved by any means in every conceivable context.


  Yde Venema (UvA)
  Coalgebra Atomata (towards a Universal Theory of Automata)
Automata operating on infinite objects provide an invaluable tool for the
specification and verification of the ongoing behavior of infinite systems.
Coalgebra automata generalize the well-known automata that operate on
specific types of infinite structures such as words/streams, trees, graphs or
transition systems. The motivation underlying the introduction of coalgebra
automata is to gain a deeper understanding of this branch of automata theory
by studying properties of automata in a uniform manner, parametric in the type
of the recognized structures. Coalgebraic automata theory thus contributes to
Universal Coalgebra as a mathematical theory of state-based evolving systems.

In the talk we give a quick introduction to coalgebra, and we introduce the
notion of a coalgebra automaton. We will see that in fact a large part of the
theory of parity automata can be lifted to a coalgebraic level of generality,
and thus indeed belongs to the theory of Universal Coalgebra.
More specifically,coalgebra automata satisfy various closure properties:
under some conditions on the coalgebraic type, the collection of recognizable
languages are closed under taking union, intersection, complementation,
and existential projections.
These results have many applications in the theory of coalgebraic fixpoint
logics (which we will not discuss).


  John Hitchcock (University of Wyoming and CWI)
  Density and Complexity of Instances in NP-Complete Sets

There is large body of research in computational complexity about the
density of complete sets for complexity classes.  This direction was
suggested by Berman and Hartmanis in 1977 when they showed that all known
NP-complete sets are polynomial-time isomorphic.  As SAT has exponential
density, it follows that all known NP-complete sets are exponentially
dense.  Is this true for every NP-complete set? This talk will give an
introduction to the research on this question
and present our recent result that the answer is yes unless the
polynomial-time hierarchy collapses.
This is joint work with Harry Buhrman.