{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T06:12:30Z","timestamp":1784527950972,"version":"3.55.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T00:00:00Z","timestamp":1684800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["2211793, 1900931, 1844976, CCF-1901025, and CCF-1652824"],"award-info":[{"award-number":["2211793, 1900931, 1844976, CCF-1901025, and CCF-1652824"]}]},{"name":"Sloan Foundation Research Fellowship"},{"name":"National Science Foundation Graduate Research Fellowship","award":["DGE1745303"],"award-info":[{"award-number":["DGE1745303"]}]},{"name":"MOST","award":["107-2221-E-002-031-MY3 and 110-2223-E-002-006-MY3"],"award-info":[{"award-number":["107-2221-E-002-031-MY3 and 110-2223-E-002-006-MY3"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            Understanding the algorithmic behaviors that are\n            <jats:italic>in principle<\/jats:italic>\n            realizable in a chemical system is necessary for a rigorous understanding of the design principles of biological regulatory networks. Further, advances in synthetic biology herald the time when we will be able to rationally engineer complex chemical systems and when idealized formal models will become blueprints for engineering.\n          <\/jats:p>\n          <jats:p>\n            Coupled chemical interactions in a well-mixed solution are commonly formalized as chemical reaction networks (CRNs). However, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. Here, we study the following problem: What functions\n            <jats:italic>\n              f : \u211d\n              <jats:sup>k<\/jats:sup>\n              \u2192 \u211d\n            <\/jats:italic>\n            can be computed by a CRN, in which the CRN eventually produces the correct amount of the \u201coutput\u201d molecule, no matter the rate at which reactions proceed? This captures a previously unexplored but very natural class of computations: For example, the reaction\n            <jats:italic>\n              X\n              <jats:sub>1<\/jats:sub>\n              + X\n              <jats:sub>2<\/jats:sub>\n              \u2192 Y\n            <\/jats:italic>\n            can be thought to compute the function\n            <jats:italic>y<\/jats:italic>\n            = min (\n            <jats:italic>\n              x\n              <jats:sub>1<\/jats:sub>\n              , x\n              <jats:sub>2<\/jats:sub>\n            <\/jats:italic>\n            ). Such a CRN is robust in the sense that it is correct whether its evolution is governed by the standard model of mass-action kinetics, alternatives such as Hill-function or Michaelis-Menten kinetics, or other arbitrary models of chemistry that respect the (fundamentally digital) stoichiometric constraints (what are the reactants and products?).\n          <\/jats:p>\n          <jats:p>\n            We develop a reachability relation based on a broad notion of \u201cwhat could happen\u201d if reaction rates can vary arbitrarily over time. Using reachability, we define\n            <jats:italic>stable computation<\/jats:italic>\n            analogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limit\n            <jats:italic>t<\/jats:italic>\n            \u2192 \u221e under a wide class of generalized rate laws. Besides the direct mapping of a concentration to a nonnegative analog value, we also consider the \u201cdual-rail representation\u201d that can represent negative values as the difference of two concentrations and allows the composition of CRN modules. We prove that a function is rate-independently computable if and only if it is piecewise linear (with rational coefficients) and continuous (dual-rail representation), or non-negative with discontinuities occurring only when some inputs switch from zero to positive (direct representation). The many contexts where continuous piecewise linear functions are powerful targets for implementation, combined with the systematic construction we develop for computing these functions, demonstrate the potential of rate-independent chemical computation.\n          <\/jats:p>","DOI":"10.1145\/3590776","type":"journal-article","created":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T12:00:55Z","timestamp":1680696055000},"page":"1-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Rate-independent Computation in Continuous Chemical Reaction Networks"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6171-9962","authenticated-orcid":false,"given":"Ho-Lin","family":"Chen","sequence":"first","affiliation":[{"name":"National Taiwan University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3922-172X","authenticated-orcid":false,"given":"David","family":"Doty","sequence":"additional","affiliation":[{"name":"University of California, Davis, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9871-3020","authenticated-orcid":false,"given":"Wyatt","family":"Reeves","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2585-4120","authenticated-orcid":false,"given":"David","family":"Soloveichik","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"e_1_3_4_2_2","first-page":"2560","volume-title":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Alistarh Dan","year":"2017","unstructured":"Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. 2017. Time-space trade-offs in population protocols. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2560\u20132579."},{"key":"e_1_3_4_3_2","first-page":"2221","volume-title":"29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Alistarh Dan","year":"2018","unstructured":"Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-optimal majority in population protocols. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms. 2221\u20132239."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3289137.3289150"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2006.376698"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2007.07.003"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146425"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_3_4_10_2","first-page":"98","article-title":"An introduction to population protocols","volume":"93","author":"Aspnes James","year":"2007","unstructured":"James Aspnes and Eric Ruppert. 2007. An introduction to population protocols. Bull. Europ. Assoc. Theoret. Comput. Sci. 93 (2007), 98\u2013117.","journal-title":"Bull. Europ. Assoc. Theoret. Comput. Sci."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1038\/43199"},{"key":"e_1_3_4_12_2","first-page":"141:1\u2013141:14","volume-title":"44th International Colloquium on Automata, Languages, and Programming (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"80","author":"Belleville Amanda","year":"2017","unstructured":"Amanda Belleville, David Doty, and David Soloveichik. 2017. Hardness of computing and approximating predicates and functions with leaderless population protocols. In 44th International Colloquium on Automata, Languages, and Programming (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 80. 141:1\u2013141:14."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3127496"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-018-9723-9"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-010-9236-7"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1038\/srep00656"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-017-9641-2"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2019.2952836"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-013-9393-6"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554827"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1038\/nnano.2013.189"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88869-7_27"},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1109\/FOCS52979.2021.00120","volume-title":"IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Czerwi\u0144ski Wojciech","year":"2022","unstructured":"Wojciech Czerwi\u0144ski and \u0141ukasz Orlikowski. 2022. Reachability in vector addition systems is Ackermann-complete. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 1229\u20131240."},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60327-4_4"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85633-5_16"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0281-z"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.032"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67471-1_7"},{"key":"e_1_3_4_29_2","first-page":"2653","volume-title":"29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"G\u0105sieniec Leszek","year":"2018","unstructured":"Leszek G\u0105sieniec and Grzegorz Staehowiak. 2018. Fast space optimal leader election in population protocols. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2653\u20132667."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1021\/j100540a008"},{"issue":"0","key":"e_1_3_4_31_2","first-page":"25","article-title":"A projection argument for differential inclusions, with applications to persistence of mass-action kinetics","volume":"9","author":"Gopalkrishnan Manoj","year":"2013","unstructured":"Manoj Gopalkrishnan, Ezra Miller, and Anne Shiu. 2013. A projection argument for differential inclusions, with applications to persistence of mass-action kinetics. Symm., Integrabil. Geom.: Meth. Applic. 9, 0 (2013), 25\u201325.","journal-title":"Symm., Integrabil. Geom.: Meth. Applic."},{"key":"e_1_3_4_32_2","volume-title":"26th International Conference on DNA Computing and Molecular Programming (DNA\u201920)","author":"Hashemi Hooman","year":"2020","unstructured":"Hooman Hashemi, Ben Chugg, and Anne Condon. 2020. Composable computation in leaderless, discrete chemical reaction networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA\u201920). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1179047"},{"key":"e_1_3_4_34_2","volume-title":"Introductory Functional Analysis with Applications","author":"Kreyszig Erwin","year":"1991","unstructured":"Erwin Kreyszig. 1991. Introductory Functional Analysis with Applications, Vol. 17. John Wiley & Sons."},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1678692"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DNA.2020.5"},{"key":"e_1_3_4_37_2","volume-title":"Introduction to Smooth Manifolds (2nd ed.)","author":"Lee John M.","year":"2013","unstructured":"John M. Lee. 2013. Introduction to Smooth Manifolds (2nd ed.). Springer."},{"key":"e_1_3_4_38_2","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1109\/FOCS52979.2021.00121","volume-title":"IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Leroux J\u00e9r\u00f4me","year":"2022","unstructured":"J\u00e9r\u00f4me Leroux. 2022. The reachability problem for Petri nets is not primitive recursive. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 1241\u20131252."},{"key":"e_1_3_4_39_2","volume-title":"The Reachability Problem Requires Exponential Space","author":"Lipton Richard J.","year":"1976","unstructured":"Richard J. Lipton. 1976. The Reachability Problem Requires Exponential Space. Technical Report. Yale University."},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213029"},{"key":"e_1_3_4_41_2","unstructured":"James R. Munkres. 2000. Topology (2nd ed.). Prentice Hall Upper Saddle River NJ 108\u2013109."},{"key":"e_1_3_4_42_2","first-page":"41","article-title":"Games with perfect information","volume":"1","author":"Mycielski Jan","year":"1992","unstructured":"Jan Mycielski. 1992. Games with perfect information. Handb. Game Theor. Econ. Applic. 1 (1992), 41\u201370.","journal-title":"Handb. Game Theor. Econ. Applic."},{"issue":"1","key":"e_1_3_4_43_2","first-page":"297","article-title":"Max-min representation of piecewise linear functions","volume":"43","author":"Ovchinnikov Sergei","year":"2002","unstructured":"Sergei Ovchinnikov. 2002. Max-min representation of piecewise linear functions. Contrib. Algeb. Geom. 43, 1 (2002), 297\u2013302.","journal-title":"Contrib. Algeb. Geom."},{"key":"e_1_3_4_44_2","volume-title":"Real Analysis (4th ed.)","author":"Royden Halsey Lawrence","year":"1988","unstructured":"Halsey Lawrence Royden and Patrick Fitzpatrick. 1988. Real Analysis (4th ed.), Vol. 32. Macmillan New York."},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1021\/acssynbio.5b00163"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1038\/nbt1253"},{"key":"e_1_3_4_47_2","first-page":"144","volume-title":"International Workshop on DNA-based Computers","author":"Seelig Georg","year":"2009","unstructured":"Georg Seelig and David Soloveichik. 2009. Time-complexity of multilayered DNA strand displacement circuits. In International Workshop on DNA-based Computers. Springer, 144\u2013153."},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0021414"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00378-z"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-008-9067-y"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0909380107"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aal2052"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2111552119"},{"key":"e_1_3_4_54_2","doi-asserted-by":"crossref","unstructured":"G\u00fcnter M. Ziegler. 1995. Lectures on Polytopes. Springer-Verlag New York.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3590776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3590776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:26Z","timestamp":1750178186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3590776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,23]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3590776"],"URL":"https:\/\/doi.org\/10.1145\/3590776","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,23]]},"assertion":[{"value":"2021-08-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}