Computational self-assembly

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.