# Theoretical computer science amsterdam (TCSA)

10/30/2009

VU

Theoretical Computer Science Amsterdam Day "(TCSA Day)"

Faculty of Science

Sciences

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

10:00-16:30

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:

http://www.vu.nl/nl/over-de-vu/contact-routebeschrijving/routebeschrijvingen/index.asp

Then the talks are in the Faculty of Medicine

which is building number 6 on the following campus-map:

http://www.vu.nl/nl/Images/plattegrond3d_tcm9-209.pdf

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:

http://www.few.vu.nl/nl/nieuws-agenda/agenda/2009/theoretical-computer-science-amsterdam-day.asp

kind regards,

the organizers:

Alban Ponse (a.ponse@uva.nl)

Femke van Raamsdonk (femke@cs.vu.nl)

Leen Torenvliet (l.torenvliet@uva.nl)

Ronald de Wolf (Ronald.de.Wolf@cwi.nl)

*********************************************************************

*********************************************************************

Abstracts of the talks of the first TCSA Day on October 30, 2009:

*********************************************************************

*********************************************************************

10:00-10:45

speaker:

Wan Fokkink (VU)

title:

Analysis of C. elegans Vulval Development using Petri Nets

abstract:

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.

*********************************************************************

*********************************************************************

11:15-11:45

speaker:

Christian Schaffner (CWI)

title:

Quantum Cryptography

abstract:

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.

*********************************************************************

*********************************************************************

11:45-12:15

speaker:

Joerg Endrullis (VU)

title:

Productivity and The Pebbleflow Method

abstract:

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 http://infinity.few.vu.nl/productivity/ .

This includes an implementation of the decision algorithm

and a animation tool visualizing the data flow in pebbleflow nets.

*********************************************************************

*********************************************************************

13:30-14:15

speaker:

Jan Bergstra (UvA)

title:

From Material Division to the off-line Halting Problem

abstract:

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.

*********************************************************************

*********************************************************************

14:15-15:00

speaker:

Yde Venema (UvA)

title:

Coalgebra Atomata (towards a Universal Theory of Automata)

abstract:

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).

*********************************************************************

*********************************************************************

15:30-16:15

speaker:

John Hitchcock (University of Wyoming and CWI)

title:

Density and Complexity of Instances in NP-Complete Sets

abstract:

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.

*********************************************************************

*********************************************************************