{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:50:43Z","timestamp":1725936643093},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_15","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T11:45:34Z","timestamp":1513856734000},"page":"212-226","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational Complexity of Atomic Chemical Reaction Networks"],"prefix":"10.1007","author":[{"given":"David","family":"Doty","sequence":"first","affiliation":[]},{"given":"Shaopeng","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-94-017-9041-3_1","volume-title":"A Systems Theoretic Approach to Systems and Synthetic Biology I: Models and System Characterizations","author":"L Adleman","year":"2014","unstructured":"Adleman, L., Gopalkrishnan, M., Huang, M.-D., Moisset, P., Reishus, D.: On the mathematics of the law of mass action. In: Kulkarni, V.V., Stan, G.-B., Raman, K. (eds.) A Systems Theoretic Approach to Systems and Synthetic Biology I: Models and System Characterizations, pp. 3\u201346. Springer, Dordrecht (2014). https:\/\/doi.org\/10.1007\/978-94-017-9041-3_1"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.: Time-space trade-offs in molecular computation. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2560\u20132579 (2017)","DOI":"10.1137\/1.9781611974782.169"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1016\/j.mbs.2007.07.003","volume":"210","author":"D Angeli","year":"2007","unstructured":"Angeli, D., De Leenheer, P., Sontag, E.D.: A Petri net approach to the study of persistence in chemical reaction networks. Math. Biosci. 210, 598\u2013618 (2007)","journal-title":"Math. Biosci."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235\u2013253 (2006). https:\/\/doi.org\/10.1007\/s00446-005-0138-3 . Preliminary version appeared in PODC 2004","journal-title":"Distrib. Comput."},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-319-43994-5_4","volume-title":"DNA Computing and Molecular Programming","author":"R Brijder","year":"2016","unstructured":"Brijder, R., Doty, D., Soloveichik, D.: Robustness of expressivity in chemical reaction networks. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 52\u201366. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-43994-5_4"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Cardelli, L., Csik\u00e1sz-Nagy, A.: The cell cycle switch computes approximate majority. Sci. Rep. 2 (2012)","DOI":"10.1038\/srep00656"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Chen, H., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. Distributed Computing (2015, to appear). Special issue of invited papers from DISC 2014","DOI":"10.1007\/978-3-662-45174-8_2"},{"issue":"4","key":"15_CR8","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s11047-013-9393-6","volume":"13","author":"HL Chen","year":"2013","unstructured":"Chen, H.L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13(4), 517\u2013534 (2013). Special issue of invited papers from DNA 2012","journal-title":"Nat. Comput."},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Chen, H.L., Doty, D., Soloveichik, D.: Rate-independent computation in continuous chemical reaction networks. In: ITCS 2014: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 313\u2013326 (2014)","DOI":"10.1145\/2554797.2554827"},{"issue":"10","key":"15_CR10","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1038\/nnano.2013.189","volume":"8","author":"YJ Chen","year":"2013","unstructured":"Chen, Y.J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755\u2013762 (2013)","journal-title":"Nat. Nanotechnol."},{"issue":"2","key":"15_CR11","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s10107-014-0823-8","volume":"153","author":"S Chubanov","year":"2015","unstructured":"Chubanov, S.: A polynomial projection algorithm for linear feasibility problems. Math. Program. 153(2), 687\u2013713 (2015)","journal-title":"Math. Program."},{"issue":"11","key":"15_CR12","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1016\/j.jsc.2008.08.006","volume":"44","author":"G Craciun","year":"2009","unstructured":"Craciun, G., Dickenstein, A., Shiu, A., Sturmfels, B.: Toric dynamical systems. J. Symb. Computat. 44(11), 1551\u20131565 (2009)","journal-title":"J. Symb. Computat."},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Cummings, R., Doty, D., Soloveichik, D.: Probability 1 computation with chemical reaction networks. Nat. Comput. 1\u201317 (2015). https:\/\/dx.doi.org\/10.1007\/s11047-015-9501-x . Special issue of invited papers from DNA 2014","DOI":"10.1007\/s11047-015-9501-x"},{"key":"15_CR14","unstructured":"Deshpande, A., Gopalkrishnan, M.: Autocatalysis in reaction networks. arXiv preprint arXiv:1309.3957 (2013)"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Doty, D.: Timing in chemical reaction networks. In: SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 772\u2013784, January 2014","DOI":"10.1137\/1.9781611973402.57"},{"issue":"2","key":"15_CR16","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s11047-014-9435-8","volume":"14","author":"D Doty","year":"2015","unstructured":"Doty, D., Hajiaghayi, M.: Leaderless deterministic chemical reaction networks. Nat. Comput. 14(2), 213\u2013223 (2015). Preliminary version appeared in DNA","journal-title":"Nat. Comput."},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Doty, D., Zhu, S.: Computational complexity of atomic chemical reaction networks. arXiv preprint arXiv:1702.05704 (2017)","DOI":"10.1007\/978-3-319-73117-9_15"},{"key":"15_CR18","first-page":"1","volume":"54","author":"J Esparza","year":"2016","unstructured":"Esparza, J., Ganty, P., Leroux, J., Majumdar, R.: Verification of population protocols. Acta Inform. 54, 1\u201325 (2016)","journal-title":"Acta Inform."},{"key":"15_CR19","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman, New York (1979)"},{"issue":"2","key":"15_CR20","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16(2), 285\u2013296 (1966). http:\/\/projecteuclid.org\/euclid.pjm\/1102994974","journal-title":"Pac. J. Math."},{"issue":"10","key":"15_CR21","doi-asserted-by":"crossref","first-page":"2137","DOI":"10.1007\/s10910-011-9896-2","volume":"49","author":"G Gnacadja","year":"2011","unstructured":"Gnacadja, G.: Reachability, persistence, and constructive chemical reaction networks (part II): a formalism for species composition in chemical reaction network theory and application to persistence. J. Math. Chem. 49(10), 2137 (2011)","journal-title":"J. Math. Chem."},{"key":"15_CR22","unstructured":"Gopalkrishnan, M.: Private communication. Email (2016)"},{"key":"15_CR23","unstructured":"Guldberg, C.M., Waage, P.: Studies concerning affinity. In: Forhandlinger: Videnskabs-Selskabet i Christinia, p. 35. Norwegian Academy of Science and Letters (1864)"},{"key":"15_CR24","unstructured":"Horn, F.J.M.: The dynamics of open reaction systems. In: SIAM-AMS Proceedings VIII, pp. 125\u2013137 (1974)"},{"issue":"5","key":"15_CR25","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1021\/sb300087n","volume":"2","author":"H Jiang","year":"2013","unstructured":"Jiang, H., Salehi, S.A., Riedel, M.D., Parhi, K.K.: Discrete-time signal processing with DNA. ACS Synth. Bafiology 2(5), 245\u2013254 (2013)","journal-title":"ACS Synth. Bafiology"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-21254-3_3","volume-title":"Language and Automata Theory and Applications","author":"J Leroux","year":"2011","unstructured":"Leroux, J.: Vector addition system reachability problem: a short self-contained proof. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 41\u201364. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21254-3_3"},{"issue":"2","key":"15_CR27","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0020-0255(76)91010-0","volume":"10","author":"YE Lien","year":"1976","unstructured":"Lien, Y.E.: A note on transition systems. Inf. Sci. 10(2), 347\u2013362 (1976)","journal-title":"Inf. Sci."},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-319-07734-5_17","volume-title":"Application and Theory of Petri Nets and Concurrency","author":"EW Mayr","year":"2014","unstructured":"Mayr, E.W., Weihmann, J.: A framework for classical Petri net problems: conservative Petri nets as an application. In: Ciardo, G., Kindler, E. (eds.) PETRI NETS 2014. LNCS, vol. 8489, pp. 314\u2013333. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07734-5_17"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"Montagne, K., Plasson, R., Sakai, Y., Fujii, T., Rondelez, Y.: Programming an in vitro DNA oscillator using a molecular networking strategy. Mol. Syst. Biol. 7(1) (2011)","DOI":"10.1038\/msb.2011.12"},{"key":"15_CR30","unstructured":"Napp, N.E., Adams, R.P.: Message passing inference with chemical reaction networks. In: Advances in Neural Information Processing Systems, pp. 2247\u20132255 (2013)"},{"issue":"4","key":"15_CR31","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1049\/iet-syb.2010.0056","volume":"5","author":"K Oishi","year":"2011","unstructured":"Oishi, K., Klavins, E.: Biomolecular implementation of linear I\/O systems. IET Syst. Biol. 5(4), 252\u2013260 (2011)","journal-title":"IET Syst. Biol."},{"issue":"4","key":"15_CR32","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1016\/j.copbio.2012.11.011","volume":"24","author":"A Padirac","year":"2013","unstructured":"Padirac, A., Fujii, T., Rondelez, Y.: Nucleic acids for the rational design of reaction circuits. Curr. Opin. Biotechnol. 24(4), 575\u2013580 (2013)","journal-title":"Curr. Opin. Biotechnol."},{"issue":"4","key":"15_CR33","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.H.: On the complexity of integer programming. J. ACM (JACM) 28(4), 765\u2013768 (1981)","journal-title":"J. ACM (JACM)"},{"issue":"7356","key":"15_CR34","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1038\/nature10262","volume":"475","author":"L Qian","year":"2011","unstructured":"Qian, L., Winfree, E., Bruck, J.: Neural network computation with dna strand displacement cascades. Nature 475(7356), 368\u2013372 (2011)","journal-title":"Nature"},{"issue":"6034","key":"15_CR35","doi-asserted-by":"crossref","first-page":"1196","DOI":"10.1126\/science.1200520","volume":"332","author":"L Qian","year":"2011","unstructured":"Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034), 1196 (2011)","journal-title":"Science"},{"key":"15_CR36","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1021\/acssynbio.5b00163","volume":"6","author":"SA Salehi","year":"2016","unstructured":"Salehi, S.A., Parhi, K.K., Riedel, M.D.: Chemical reaction networks for computing polynomials. ACS Synth. Biol. 6, 76\u201383 (2016)","journal-title":"ACS Synth. Biol."},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Salehi, S.A., Riedel, M.D., Parhi, K.K.: Asynchronous discrete-time signal processing with molecular reactions. In: 2014 48th Asilomar Conference on Signals, Systems and Computers, pp. 1767\u20131772. IEEE (2014)","DOI":"10.1109\/ACSSC.2014.7094771"},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Salehi, S.A., Riedel, M.D., Parhi, K.K.: Markov chain computations using molecular reactions. In: 2015 IEEE International Conference on Digital Signal Processing (DSP), pp. 689\u2013693. IEEE (2015)","DOI":"10.1109\/ICDSP.2015.7251963"},{"issue":"2","key":"15_CR39","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5805","key":"15_CR40","doi-asserted-by":"crossref","first-page":"1585","DOI":"10.1126\/science.1132493","volume":"314","author":"G Seelig","year":"2006","unstructured":"Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585\u20131588 (2006). http:\/\/www.sciencemag.org\/cgi\/doi\/10.1126\/science.1132493","journal-title":"Science"},{"key":"15_CR41","volume-title":"Operating System Concepts","author":"A Silberschatz","year":"2013","unstructured":"Silberschatz, A., Galvin, P.B., Gagne, G., Silberschatz, A.: Operating System Concepts. Addison-Wesley, Reading (2013)"},{"issue":"4","key":"15_CR42","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s11047-008-9067-y","volume":"7","author":"D Soloveichik","year":"2008","unstructured":"Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615\u2013633 (2008). https:\/\/doi.org\/10.1007\/s11047-008-9067-y","journal-title":"Nat. Comput."},{"issue":"12","key":"15_CR43","doi-asserted-by":"crossref","first-page":"5393","DOI":"10.1073\/pnas.0909380107","volume":"107","author":"D Soloveichik","year":"2010","unstructured":"Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Nat. Acad. Sci. 107(12), 5393 (2010). Preliminary version appeared in DNA 2008","journal-title":"Proc. Nat. Acad. Sci."},{"key":"15_CR44","unstructured":"Srinivas, N.: Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement. Ph.D. thesis, California Institute of Technology (2015)"},{"key":"15_CR45","doi-asserted-by":"crossref","unstructured":"Thachuk, C., Condon, A.: Space and energy efficient computation with DNA strand displacement systems. In: DNA 2012: Proceedings of the 18th International Meeting on DNA Computing and Molecular Programming, pp. 135\u2013149 (2012)","DOI":"10.1007\/978-3-642-32208-2_11"},{"issue":"6796","key":"15_CR46","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1038\/35020524","volume":"406","author":"B Yurke","year":"2000","unstructured":"Yurke, B., Turberfield, A., Mills Jr., A., Simmel, F., Neumann, J.: A DNA-fuelled molecular machine made of DNA. Nature 406(6796), 605\u2013608 (2000)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T20:19:09Z","timestamp":1660162749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}