Oxford logo
[CKL16a] L. Cardelli, M. Kwiatkowska, L. Laurenti. Programming Discrete Distributions with Chemical Reaction Networks. In Y. Rondelez and D. Woods (editors), Proc. 22nd International Conference on DNA Computing and Molecular Programming (DNA22), Springer. To appear. 2016. [pdf] [bib]
Downloads:  pdf pdf (472 KB)  bib bib
Notes: The original publication is available at link.springer.com.
Abstract. We explore the range of probabilistic behaviours that can be engineered with Chemical Reaction Networks (CRNs). We show that at steady state CRNs are able to "program" any distribution with fi nite support in ℕm, with m ≥ 1. Moreover, any distribution with countable in finite support can be approximated with arbitrarily small error under the L1 norm. We also give optimized schemes for special distributions, including the uniform distribution. Finally, we formulate a calculus to compute on distributions that is complete for fi nite support distributions, and can be compiled to a restricted class of CRNs that at steady state realize those distributions.