A Caltech Library Service

Verifying Chemical Reaction Network Implementations: A Bisimulation Approach

Johnson, Robert F. and Dong, Qing and Winfree, Erik (2016) Verifying Chemical Reaction Network Implementations: A Bisimulation Approach. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.9818. Springer , Cham, pp. 114-134. ISBN 9783319439938.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Efforts in programming DNA and other biological molecules have recently focused on general schemes to physically implement arbitrary Chemical Reaction Networks. Errors in some of the proposed schemes have driven a desire for formal verification methods. We show that by interpreting each implementation species as a set of formal species, the concept of weak bisimulation can be adapted to CRNs in a way that agrees with an intuitive notion of a correct implementation. We give examples of how to use bisimulation to prove the correctness of an implementation or detect subtle problems. We examine the complexity of finding a valid interpretation between two CRNs if one exists, and that of checking whether an interpretation is valid. We show that both are PSPACE-complete in the general case, but are NP-complete and polynomial-time respectively under an assumption that holds in many practical cases. We give algorithms for both of those problems.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2016 Springer International Publishing Switzerland. First Online 14 August 2016. The authors would like to thank Chris Thachuk, Damien Woods, Dave Doty, and Seung Woo Shin for helpful discussions. RFJ and EW were supported by NSF grants 1317694, 1213127, and 0832824. RFJ was supported by Caltech’s Summer Undergraduate Research Fellowship program and an NSF graduate fellowship. QD’s current affiliation is Epic Systems, Madison, Wisconsin.
Funding AgencyGrant Number
Caltech Summer Undergraduate Research Fellowship (SURF)UNSPECIFIED
NSF Graduate Research FellowshipUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:9818
Record Number:CaltechAUTHORS:20191007-155606936
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99129
Deposited By: Tony Diaz
Deposited On:07 Oct 2019 23:07
Last Modified:07 Oct 2019 23:07

Repository Staff Only: item control page