Programming discrete distributions with chemical reaction networks

DOI10.1007/978-3-319-43994-5_3MaRDI QIDQ2835702zbMATH OpenOpenAlexWikidataFDO

Authors Luca Cardelli, Marta Kwiatkowska, Luca Laurenti

Publication date 30 November 2016

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

Full work available at URL https://arxiv.org/abs/1601.02578, https://ora.ox.ac.uk/objects/uuid:7e6f1b5d-e4e3-4177-92a3-a70b14fdb778

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)

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.

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

Cites work

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

Cited in

(15)

• Multi-scale verification of distributed synchronisation
• Reachability bounds for chemical reaction networks and strand displacement systems
• 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
• 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
• On design and analysis of chemical reaction network algorithms
• Stochastic games with synchronizing objectives
• 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)