Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks
Tóm tắt
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 consensus-based output convention have equivalent computational power to (1) existence-based and (2) democracy-based output conventions. The CRNs using the former output convention have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The CRNs using the latter output convention 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 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.
Tài liệu tham khảo
Alistarh D, Gelashvili R (2015) Polylogarithmic-time leader election in population protocols. In: ICALP 2015: proceedings of the 42nd international colloquium on automata, languages, and programming, Kyoto, Japan
Alistarh D, Aspnes J, Eisenstat D, Gelashvili R, Rivest RL (2016) Time-space trade-offs in population protocols. Technical Report. arXiv:1602.08032
Alistarh D, Dudek B, Kosowski A, Soloveichik D, Uznański P (2017) Robust detection in leak-prone population protocols. Technical Report. arXiv:1706.09937
Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R (2006a) Computation in networks of passively mobile finite-state sensors. Distrib Comput 18(4):235–253
Angluin D, Aspnes J, Eisenstat D (2006b) Stably computable predicates are semilinear. In: PODC 2006: proceedings of the 25th annual ACM symposium on principles of distributed computing, New York, NY, USA. ACM Press, pp 292–299
Angluin D, Aspnes J, Eisenstat D, Ruppert E (2007) The computational power of population protocols. Distrib Comput 20(4):279–304
Angluin D, Aspnes J, Eisenstat D (2008) Fast computation by population protocols with a leader. Distrib Comput 21(3):183–199
Brijder R (2014) Output stability and semilinear sets in chemical reaction networks and deciders. In: DNA 20: proceedings of the 20th international meeting on DNA computing and molecular programming, pp 100–113
Brijder R, Doty D, Soloveichik D (2016) Robustness of expressivity in chemical reaction networks. In: Rondelez Y, Woods D (eds) DNA 22: proceedings of the 22th international meeting on DNA computing and molecular programming, vol 9818 of lecture notes in computer science. Springer, pp 52–66
Chen H-L, Doty D, Soloveichik D (2014a) Deterministic function computation with chemical reaction networks. Nat Comput 13(4):517–534
Chen HL, Doty D, Soloveichik D (2014b) Rate-independent computation in continuous chemical reaction networks. In: ITCS 2014: proceedings of the 5th innovations in theoretical computer science conference, pp 313–326
Cook M, Soloveichik D, Winfree E, Bruck J (2009) Programmability of chemical reaction networks. In: Condon A, Harel D, Kok JN, Salomaa A, Winfree E (eds) Algorithmic bioprocesses, natural computing series. Springer, Berlin, pp 543–584
Cummings R, Doty D, Soloveichik D (2016) Probability 1 computation with chemical reaction networks. Nat Comput 15(2):245–261
Dickson LE (1913) Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. Am J Math 35:413–422
Doty D, Hajiaghayi M (2015) Leaderless deterministic chemical reaction networks. Nat Comput 14(2):213–223
Doty D, Soloveichik D (2015) Stable leader election in population protocols requires linear time. In: DISC 2015: proceedings of the 29th international symposium on distributed computing, lecture notes in computer science. Springer, Berlin, pp 602–616
Esparza J, Ganty P, Leroux J, Majumdar R (2015) Verification of population protocols. In: CONCUR 2015: 26th international conference on concurrency theory, vol 42, pp 470–482
Esparza J, Ganty P, Leroux J, Majumdar R (2017) Verification of population protocols. Acta Inform 54(2):191–215
Gillespie DT (1977) Exact stochastic simulation of coupled chemical reactions. J Phys Chem 81(25):2340–2361
Ginsburg S, Spanier EH (1966) Semigroups, Presburger formulas, and languages. Pac J Math 16(2):285–296
Hopcroft JE, Pansiot J-J (1979) On the reachability problem for 5-dimensional vector addition systems. Theoret Comput Sci 8:135–159
Karp RM, Miller RE (1969) Parallel program schemata. J Comput Syst Sci 3(2):147–195
Mealy GH (1955) A method for synthesizing sequential circuits. Bell Syst Tech J 34(5):1045–1079
Moore EF (1956) Gedanken-experiments on sequential machines. Autom Stud 34:129–153
Peterson JL (1977) Petri nets. ACM Comput Surv 9(3):223–252
Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615–633
Soloveichik D, Seelig G, Winfree E (2010) DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci 107(12):5393–5398