Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/23151
Title: | Robustness of Expressivity in Chemical Reaction Networks | Authors: | BRIJDER, Robert Doty, David Soloveichik, David |
Issue Date: | 2016 | Publisher: | Springer International | Source: | Rondelez, Yannick; Woods, Damien (Ed.). DNA Computing and Molecular Programming, Springer International,p. 52-66 | Series/Report: | Lecture Notes in Computer Science (LNCS) | Abstract: | We show that some natural output conventions for error-free computation in chemical reaction networks (CRN) lead to a common level of computational expressivity. Our main results are that the standard definition of error-free CRNs have equivalent computational power to 1) asymmetric and 2) democratic CRNs. The former have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The latter define output by majority vote among “yes” and “no” voters. Both results are proven via a generalized framework that simultaneously captures several definitions, directly inspired by a recent Petri net result of Esparza, Ganty, Leroux, and Majumder [CONCUR 2015]. These results support the thesis that the computational expressivity of error-free CRNs is intrinsic, not sensitive to arbitrary definitional choices. | Document URI: | http://hdl.handle.net/1942/23151 | ISBN: | 9783319439938 | DOI: | 10.1007/978-3-319-43994-5_4 | Rights: | © Springer International Publishing Switzerland 2016 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
paper_43.pdf | Peer-reviewed author version | 601.86 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Sep 2, 2020
Page view(s)
68
checked on Sep 7, 2022
Download(s)
184
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.