{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T15:30:57Z","timestamp":1770132657182,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540888680","type":"print"},{"value":"9783540888697","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-88869-7_27","type":"book-chapter","created":{"date-parts":[[2009,8,12]],"date-time":"2009-08-12T21:41:55Z","timestamp":1250113315000},"page":"543-584","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":88,"title":["Programmability of\u00a0Chemical Reaction Networks"],"prefix":"10.1007","author":[{"given":"Matthew","family":"Cook","sequence":"first","affiliation":[]},{"given":"David","family":"Soloveichik","sequence":"additional","affiliation":[]},{"given":"Erik","family":"Winfree","sequence":"additional","affiliation":[]},{"given":"Jehoshua","family":"Bruck","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,13]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"2340","DOI":"10.1021\/j100540a008","volume":"81","author":"DT Gillespie","year":"1977","unstructured":"Gillespie DT (1977) Exact stochastic simulation of coupled chemical reactions. J Phys Chem 81:2340\u20132361","journal-title":"J Phys Chem"},{"key":"27_CR2","doi-asserted-by":"crossref","first-page":"1633","DOI":"10.1093\/genetics\/149.4.1633","volume":"149","author":"AP Arkin","year":"1998","unstructured":"Arkin AP, Ross J, McAdams HH (1998) Stochastic kinetic analysis of a developmental pathway bifurcation in phage-l Escherichia coli. Genetics 149:1633\u20131648","journal-title":"Genetics"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"1876","DOI":"10.1021\/jp993732q","volume":"104","author":"M Gibson","year":"2000","unstructured":"Gibson M, Bruck J (2000) Efficient exact stochastic simulation of chemical systems with many species and many channels. J Phys Chem A 104:1876\u20131889","journal-title":"J Phys Chem A"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1002\/bies.950171112","volume":"17","author":"P Guptasarma","year":"1995","unstructured":"Guptasarma P (1995) Does replication-induced transcription regulate synthesis of the myriad low copy number proteins of Escherichia coli? Bioessays 17:987\u2013997","journal-title":"Bioessays"},{"key":"27_CR5","volume-title":"Genes VII","author":"B Levin","year":"1999","unstructured":"Levin B (1999) Genes VII. Oxford University Press, Oxford"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1073\/pnas.94.3.814","volume":"94","author":"HH McAdams","year":"1997","unstructured":"McAdams HH, Arkin AP (1997) Stochastic mechanisms in gene expression. Proc Natl Acad Sci 94:814\u2013819","journal-title":"Proc Natl Acad Sci"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1126\/science.1070919","volume":"297","author":"MB Elowitz","year":"2002","unstructured":"Elowitz MB, Levine AJ, Siggia ED, Swain PS (2002) Stochastic gene expression in a single cell. Science 297:1183\u20131185","journal-title":"Science"},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1038\/nature04588","volume":"440","author":"GM Suel","year":"2006","unstructured":"Suel GM, Garcia-Ojalvo J, Liberman LM, Elowitz MB (2006) An excitable gene regulatory circuit induces transient cellular differentiation. Nature 440:545\u2013550","journal-title":"Nature"},{"key":"27_CR9","first-page":"143","volume":"3","author":"J Esparza","year":"1994","unstructured":"Esparza J, Nielsen M (1994) Decidability issues for Petri nets\u2014a survey. J Inf Process Cybern 3:143\u2013160","journal-title":"J Inf Process Cybern"},{"issue":"4","key":"27_CR10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"RM Karp","year":"1969","unstructured":"Karp RM, Miller RE (1969) Parallel program schemata. J\u00a0Comput Syst Sci 3(4):147\u2013195","journal-title":"J\u00a0Comput Syst Sci"},{"key":"27_CR11","first-page":"49","volume-title":"Proceedings of the 1972 number theory conference","author":"JH Conway","year":"1972","unstructured":"Conway JH (1972) Unpredictable iterations. In: Proceedings of the 1972 number theory conference. University of Colorado, Boulder, pp 49\u201352"},{"key":"27_CR12","volume-title":"Fractran: a simple universal programming language for arithmetic","author":"JH Conway","year":"1987","unstructured":"Conway JH (1987) Fractran: a simple universal programming language for arithmetic. Springer, New York, chap\u00a02, pp\u00a04\u201326"},{"key":"27_CR13","volume-title":"Computation: finite and infinite machines","author":"M Minsky","year":"1967","unstructured":"Minsky M (1967) Computation: finite and infinite machines. Prentice\u2013Hall, New Jersey"},{"key":"27_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-008-9067-y","author":"D Soloveichik","year":"2008","unstructured":"Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput. doi:10.1007\/s11047-008-9067-y","journal-title":"Nat Comput"},{"key":"27_CR15","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/978-3-540-85361-9_37","volume-title":"CONCUR","author":"G Zavattaro","year":"2008","unstructured":"Zavattaro G, Cardelli L (2008) Termination problems in chemical kinetics. In: van Breugel F, Chechik M (eds) CONCUR. Lecture notes in computer science, vol\u00a05201. Springer, Berlin, pp 477\u2013491"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Liekens AML, Fernando CT (2006) Turing complete catalytic particle computers. In: Proceedings of unconventional computing conference, York","DOI":"10.1007\/978-3-540-74913-4_120"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Angluin D, Aspnes J, Eisenstat D (2006) Fast computation by population protocols with a leader. Technical Report YALEU\/DCS\/TR-1358, Yale University Department of Computer Science. Extended abstract to appear, DISC 2006","DOI":"10.1007\/11864219_5"},{"issue":"12","key":"27_CR18","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1007\/BF02084158","volume":"21","author":"CH Bennett","year":"1982","unstructured":"Bennett CH (1982) The thermodynamics of computation\u2014a review. Int J Theor Phys 21(12):905\u2013939","journal-title":"Int J Theor Phys"},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1080\/00207169508804451","volume":"59","author":"G P\u0103un","year":"1995","unstructured":"P\u0103un G (1995) On the power of the splicing operation. Int J Comput Math 59:27\u201335","journal-title":"Int J Comput Math"},{"key":"27_CR20","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-1-4612-1872-2_8","volume-title":"Complexity theory retrospective II","author":"SA Kurtz","year":"1997","unstructured":"Kurtz SA, Mahaney SR, Royer JS, Simon J (1997) Biological computing. In: Hemaspaandra LA, Selman AL (eds) Complexity theory retrospective II. Springer, Berlin, pp 179\u2013195"},{"key":"27_CR21","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/978-3-540-85101-1_6","volume-title":"AB","author":"L Cardelli","year":"2008","unstructured":"Cardelli L, Zavattaro G (2008) On the computational power of biochemistry. In: Horimoto K, Regensburger G, Rosenkranz M, Yoshida H (eds) AB. Lecture notes in computer science, vol\u00a05147. Springer, Berlin, pp 65\u201380"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Berry G, Boudol G (1990) The chemical abstract machine. In Proceedings of the 17th ACM SIGPLAN\u2013SIGACT annual symposium on principles of programming languages, pp 81\u201394","DOI":"10.1145\/96709.96717"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(02)00136-6","volume":"287","author":"G P\u0103un","year":"2002","unstructured":"P\u0103un G, Rozenberg G (2002) A guide to membrane computing. Theor Comput Sci 287:73\u2013100","journal-title":"Theor Comput Sci"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"1190","DOI":"10.1103\/PhysRevLett.78.1190","volume":"78","author":"MO Magnasco","year":"1997","unstructured":"Magnasco MO (1997) Chemical kinetics is Turing universal. Phys Rev Lett 78:1190\u20131193","journal-title":"Phys Rev Lett"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"10983","DOI":"10.1073\/pnas.88.24.10983","volume":"88","author":"A Hjelmfelt","year":"1991","unstructured":"Hjelmfelt A, Weinberger ED, Ross J (1991) Chemical implementation of neural networks and Turing machines. Proc Natl Acad Sci 88:10983\u201310987","journal-title":"Proc Natl Acad Sci"},{"key":"27_CR26","unstructured":"Petri CA (1962) Kommunikation mit Automaten. Technical Report Schriften des IMM No 2. Institut f\u00fcr Instrumentelle Mathematik, Bonn"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"6750","DOI":"10.1073\/pnas.95.12.6750","volume":"95","author":"PJE Goss","year":"1998","unstructured":"Goss PJE, Peccoud J (1998) Quantitative modeling of stochastic systems in molecular biology by using stochastic Petri nets. Proc Natl Acad Sci USA 95:6750\u20136755","journal-title":"Proc Natl Acad Sci USA"},{"key":"27_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF00289268","volume":"15","author":"EW Mayr","year":"1981","unstructured":"Mayr EW (1981) Persistence of vector replacement systems is decidable. Acta Inform 15:309\u2013318","journal-title":"Acta Inform"},{"key":"27_CR29","doi-asserted-by":"crossref","unstructured":"Sacerdote GS, Tenney RL (1977) The decidability of the reachability problem for vector addition systems (preliminary version). In: 9th annual symposium on theory of computing, Boulder, pp 61\u201376","DOI":"10.1145\/800105.803396"},{"key":"27_CR30","volume-title":"On the two-valued iterative systems of mathematical logic","author":"EL Post","year":"1941","unstructured":"Post EL (1941) On the two-valued iterative systems of mathematical logic. Princeton University Press, New Jersey"},{"key":"27_CR31","unstructured":"Cook M (2005) Networks of relations. PhD thesis, California Institute of Technology"},{"key":"27_CR32","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0022-0000(86)90006-1","volume":"32","author":"LE Rosier","year":"1986","unstructured":"Rosier LE, Yen H-C (1986) A multiparameter analysis of the boundedness problem for vector addition systems. J Comput Syst Sci 32:105\u2013135","journal-title":"J Comput Syst Sci"},{"key":"27_CR33","unstructured":"Skolem T (1923) Begr\u00fcndung der elementaren Arithmetik durch die rekurrierende Denkweise ohne anwendung scheinbarer Ver\u00e4nderlichen mit unendlichem Ausdehnungsbereich. Videnskapsselskapets Skrifter.\u00a01. Matematisk-naturvidenskabelig Klasse,\u00a06"},{"key":"27_CR34","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01700692","volume":"38","author":"K G\u00f6del","year":"1931","unstructured":"G\u00f6del K (1931) \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme, I. Monatschefte Math Phys 38:173\u2013198","journal-title":"Monatschefte Math Phys"},{"issue":"2","key":"27_CR35","first-page":"230","volume":"42","author":"A Turing","year":"1936\u20131937","unstructured":"Turing A (1936\u20131937) On computable numbers, with and application to the Entscheidungsproblem. Proc Lond Math Soc 42(2):230\u2013265","journal-title":"Proc Lond Math Soc"},{"key":"27_CR36","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W Ackermann","year":"1928","unstructured":"Ackermann W (1928) Zum hilbertschen Aufbau der reellen Zahlen. Math Ann 99:118\u2013133","journal-title":"Math Ann"},{"key":"27_CR37","first-page":"1","volume":"166","author":"J Herbrand","year":"1931","unstructured":"Herbrand J (1931) Sur la non-contradiction de l\u2019arithm\u00e9tique. J Reine Angew Math 166:1\u20138","journal-title":"J Reine Angew Math"},{"key":"27_CR38","first-page":"39","volume-title":"The undecidable","author":"K G\u00f6del","year":"1934","unstructured":"G\u00f6del K (1934) On undecidable propositions of formal mathematical systems. In: Davis M (ed) The undecidable. Springer, Berlin, pp 39\u201374. Lecture notes taken by Kleene and Rosser at Princeton"},{"key":"27_CR39","doi-asserted-by":"publisher","first-page":"345","DOI":"10.2307\/2371045","volume":"58","author":"A Church","year":"1936","unstructured":"Church A (1936) An unsolvable problem of elementary number theory. Am J Math 58:345\u2013363","journal-title":"Am J Math"},{"key":"27_CR40","volume-title":"Rekursive funktionen","author":"R P\u00e9ter","year":"1951","unstructured":"P\u00e9ter R (1951) Rekursive funktionen. Akad\u00e9miai Kiad\u00f3, Budapest"},{"key":"27_CR41","doi-asserted-by":"publisher","first-page":"876","DOI":"10.2307\/2319446","volume":"81","author":"D Gale","year":"1974","unstructured":"Gale D (1974) A curious nim-type game. Am Math Mon 81:876\u2013879","journal-title":"Am Math Mon"},{"key":"27_CR42","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky ML (1961) Recursive unsolvability of Post\u2019s problem of \u2018tag\u2019 and other topics in theory of Turing machines. Ann Math 74:437\u2013455","journal-title":"Ann Math"},{"key":"27_CR43","unstructured":"Neary T, Woods D (2005) A small fast universal Turing machine. Technical Report NUIM-CS-2005-TR-12, Dept. of Computer Science, NUI Maynooth"},{"key":"27_CR44","unstructured":"Soloveichik D (2008) Robust stochastic chemical reaction networks and bounded tau-leaping. arXiv:0803.1030v1"},{"key":"27_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.25088\/ComplexSystems.15.1.1","volume":"15","author":"M Cook","year":"2004","unstructured":"Cook M (2004) Universality in elementary cellular automata. Complex Syst 15:1\u201340","journal-title":"Complex Syst"},{"key":"27_CR46","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/978-3-540-24628-2_11","volume-title":"DNA computing 9","author":"M Cook","year":"2004","unstructured":"Cook M, Rothemund PWK (2004) Self-assembled circuit patterns. In: Winfree E (ed) DNA computing 9, vol\u00a02943. Springer, Berlin, pp 91\u2013107"}],"container-title":["Natural Computing Series","Algorithmic Bioprocesses"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88869-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T18:42:31Z","timestamp":1739299351000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-88869-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540888680","9783540888697"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88869-7_27","relation":{},"ISSN":["1619-7127"],"issn-type":[{"value":"1619-7127","type":"print"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"13 August 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}