[11-2]Computational self-assembly

Date:2007-12-27

Title: Computational self-assembly
Speaker: Prof. Pierre-Louis Curien
         CNRS & Universite Paris 7
         (joint work with Vincent Danos and  Min Zhang)

Time:    10am, Friday Nov 2
Venue:   Lecture room, Lab for Computer Science, Level 3 Building #5, Institute of Software, CAS

Abstract:

The object of this paper is to appreciate the computational limits inherent in the combinatorics of an applied concurrent language к. That language is primarily meant as a visual and concise notation for biological signalling pathways. Descriptions in к, when enriched with suitable kinetic information, generate simulations as continuous time Markov chains. However, к can be studied independently of the intended application, in a purely computational fashion, and this is what we are doing here.
Specifically, we define a compilation of к into a language where interactions can involve at most two agents at a time. That compilation is generic, the blow up in the number of rules is linear in the total rule set size, and the methodology used in deriving the compilation relies on an implicit causality analysis. The correctness proof is given in details, and correctness is spelt out in terms of the existence of a specific weak bisimulation. To compensate for the create unique identifiers. An interesting by-product of the analysis is that when using acyclic rules, one sees that name creation is not needed, and к can be fully reduced to binary form.