Algorithmic chemical reaction networks
Organizer and Chair: Dave Doty
(California Institute of Technology, USA)
- ROBERT BRIJDER, Hasselt University, Belgium
Determining final outputs of CRNs efficiently [PDF]
In the discrete chemical reaction network (CRN) model of Chen et al., for each given input there is a deterministic final output. A problem however is that the output of the network may change many times until its output is final.
In this talk we are concerned with the problem of determining whether or not the output is final, in other words, whether or not the output may change in the future. We show that the subclass of bimolecular CRNs has interesting properties for this problem. We also focus on open problems.
- ANNE CONDON, University of British Columbia
CRN Pseudocode as a tool for writing deterministic, reversible CRNs [PDF]
A nice property of CRNs with reversible reactions is that they can deterministically and reversibly simulate deterministic algorithms in a time- and space-efficient manner. However, writing such CRN
simulations can be tricky. Weâ€™ll describe how to express such simulations in a more natural CRN pseudo-code, and how CRN pseudo-code can then be automatically translated into an equivalent formal CRN that is deterministically reversible if the CRN pseudo-code is.
- ROBERT JOHNSON, California Institute of Technology
Using Bisimulation for Verification of Chemical Reaction Network Implementations [PDF]
An important aspect of the use of Chemical Reaction Networks as a programming language is the ability to compile a CRN into a physical implementation and verify that the implementation is correct. The concept of bisimulation between concurrent systems can be adapted to verify implementations of finite Chemical Reaction Networks. This concept can be further adapted to Polymer Reaction Networks, an extended model which allows unbounded linear polymers. We show the use of bisimulation to prove certain interesting systems correct or detect errors. We also discuss the computational complexity of checking a CRN or PRN implementation using bisimulation.
- DAVID SOLOVEICHIK, University of California, San Francisco
Speed faults in computation by chemical reaction networks [PDF]
The challenge of fast information processing in CRNs is to ensure that we don't rely on a bottleneck "slow" reaction that requires two molecules to react, both of which are present in "low" counts. A CRN is susceptible to speed faults if states are reachable from which the correct answer may only be computed by executing a slow reaction. We show that the problems decidable by CRNs guaranteed to avoid speed faults are precisely boolean combinations of questions of the form "is a certain species present or not?" -- i.e. speed fault free CRNs can't "count" the input molecules.
- CHRIS THACHUK, California Institute of Technology
Logically reversible chemical reaction networks [PDF]
Can chemical reaction networks (CRNs) be energy efficient? To
answer that question, we can begin by determining their capacity
for logically-reversible computation. Can logically-reversible
CRNs be realized? Yes -- It has been shown in theory and
practice that arbitrary CRNs can, in principle, be emulated by
sets of interacting DNA strands. DNA strand displacement (DSD)
systems offer new challenges when implementing discrete
stochastic CRNs: their space complexity can be exponentially
larger than the CRN they implement. With some tricks, we show
how any space-bounded deterministic computation can be realized
by a space-efficient logically-reversible CRN or DSD.