Leaderless Deterministic Chemical Reaction Networks
From MaRDI portal
Abstract: This paper answers an open question of Chen, Doty, and Soloveichik [1], who showed that a function f:N^k --> N^l is deterministically computable by a stochastic chemical reaction network (CRN) if and only if the graph of f is a semilinear subset of N^{k+l}. That construction crucially used "leaders": the ability to start in an initial configuration with constant but non-zero counts of species other than the k species X_1,...,X_k representing the input to the function f. The authors asked whether deterministic CRNs without a leader retain the same power. We answer this question affirmatively, showing that every semilinear function is deterministically computable by a CRN whose initial configuration contains only the input species X_1,...,X_k, and zero counts of every other species. We show that this CRN completes in expected time O(n), where n is the total number of input molecules. This time bound is slower than the O(log^5 n) achieved in [1], but faster than the O(n log n) achieved by the direct construction of [1] (Theorem 4.1 in the latest online version of [1]), since the fast construction of that paper (Theorem 4.4) relied heavily on the use of a fast, error-prone CRN that computes arbitrary computable functions, and which crucially uses a leader.
Recommendations
- Leaderless deterministic chemical reaction networks
- Composable computation in leaderless, discrete chemical reaction networks
- A network dynamics approach to chemical reaction networks
- Output-oblivious stochastic chemical reaction networks
- Chemical reaction networks and stochastic local search
- Deterministic function computation with chemical reaction networks
- Deterministic Function Computation with Chemical Reaction Networks
- Rate-independent computation in continuous chemical reaction networks
- Concordant chemical reaction networks
- A tutorial on chemical reaction network dynamics
Cites work
- Chemical implementation of neural networks and Turing machines.
- Computation in networks of passively mobile finite-state sensors
- Computation with finite stochastic chemical reaction networks
- Deterministic Function Computation with Chemical Reaction Networks
- Fast Computation by Population Protocols with a Leader
- Less haste, less waste: on recycling and its limits in strand displacement systems
- Reachability bounds for chemical reaction networks and strand displacement systems
- Space and energy efficient computation with DNA strand displacement systems
- Stably computable predicates are semilinear
- Strand algebras for DNA computing
- Termination Problems in Chemical Kinetics
Cited in
(12)- Speed faults in computation by chemical reaction networks
- Leaderless deterministic chemical reaction networks
- How many cooks spoil the soup?
- Minimal output unstable configurations in chemical reaction networks and deciders
- Deterministic function computation with chemical reaction networks
- How Many Cooks Spoil the Soup?
- Robustness of expressivity in chemical reaction networks
- Polylogarithmic-time leader election in population protocols
- Output-oblivious stochastic chemical reaction networks
- Functional analysis of large-scale DNA strand displacement circuits
- Composable computation in leaderless, discrete chemical reaction networks
- Computing with chemical reaction networks: a tutorial
This page was built for publication: Leaderless Deterministic Chemical Reaction Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168497)
