Computational Self-assembly

Pierre-Louis Curien, Vincent Danos, Jean Krivine, Min Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

The object of this paper is to probe the computational limits of an applied concurrent language called κκ. This language describes how agents can bind and modify each other. It is meant as a syntactic medium to build, discuss and execute descriptions of cellular signalling pathways. However, it can be studied independently of its intended interpretation, and this is what we are doing here.

Specifically, we define a reduction of κκ to a fragment where interactions can involve at most two agents at a time. The translation relies on an implicit causality analysis which permits escaping deadlocks. It incurs only a linear blow up in the number of rules. Its correctness is spelt out in terms of the existence of a specific weak bisimulation and is proved in detail. To compensate for the binary restriction, one allows components to create unique names. When using acyclic rules, this additional facility of name creation is not needed and κκ can be reduced to a binary form as is.
Original languageEnglish
Pages (from-to)61-75
Number of pages15
JournalTheoretical Computer Science
Volume404
Issue number1-2
DOIs
Publication statusPublished - Sep 2008

Fingerprint Dive into the research topics of 'Computational Self-assembly'. Together they form a unique fingerprint.

Cite this