CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

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.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan