Programming discrete distributions with chemical reaction networks

DOI10.1007/978-3-319-43994-5_3zbMATH Open1451.68108arXiv1601.02578OpenAlexW2962775345WikidataQ56981832 ScholiaQ56981832MaRDI QIDQ2835702FDOQ2835702

Authors: Luca Cardelli, Marta Kwiatkowska, Luca Laurenti 

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 finite support in $mathbb{N}^m$, with $mgeq1$. Moreover, any distribution with countable infinite support can be approximated with arbitrarily small error under the $L^1$ 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 finite support distributions, and can be compiled to a restricted class of CRNs that at steady state realize those distributions.

Full work available at URL: https://arxiv.org/abs/1601.02578

Recommendations

• Stochastic chemical reaction networks for robustly approximating arbitrary probability distributions
• Deterministic function computation with chemical reaction networks
• Deterministic Function Computation with Chemical Reaction Networks
• Timing in chemical reaction networks

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Distribution theory (60E99) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Computation with finite stochastic chemical reaction networks
• The computational power of population protocols
• Deterministic function computation with chemical reaction networks
• Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface
• Stochastic model checking
• Product-form stationary distributions for deficiency zero chemical reaction networks
• Programming discrete distributions with chemical reaction networks

Cited In (15)

• Multi-scale verification of distributed synchronisation
• Deterministic Function Computation with Chemical Reaction Networks
• Reachability bounds for chemical reaction networks and strand displacement systems
• Approximate majority analyses using tri-molecular chemical reaction networks
• Reachability bounds for chemical reaction networks and strand displacement systems
• Chemical Boltzmann machines
• Composable computation in discrete chemical reaction networks
• ppsim: a software package for efficiently simulating and visualizing population protocols
• Probability 1 computation with chemical reaction networks
• Programming discrete distributions with chemical reaction networks
• Programming discrete distributions with chemical reaction networks
• Stochastic games with synchronizing objectives
• On design and analysis of chemical reaction network algorithms
• Computing with chemical reaction networks: a tutorial
• Timing in chemical reaction networks

This page was built for publication: Programming discrete distributions with chemical reaction networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835702)