Document Open Access Logo

Composable Computation in Leaderless, Discrete Chemical Reaction Networks

Authors Hooman Hashemi, Ben Chugg, Anne Condon

PDF

File

Thumbnail PDF
PDF
LIPIcs.DNA.2020.3.pdf
  • Filesize: 0.79 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Formal languages and automata theory
Keywords
  • Chemical Reaction Networks
  • Stable Function Computation
  • Output-Oblivious
  • Output-Monotonic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We classify the functions f:ℕ^d → ℕ that are stably computable by leaderless, output-oblivious discrete (stochastic) Chemical Reaction Networks (CRNs). CRNs that compute such functions are systems of reactions over species that include d designated input species, whose initial counts represent an input x ∈ ℕ^d, and one output species whose eventual count represents f(x). Chen et al. showed that the class of functions computable by CRNs is precisely the semilinear functions. In output-oblivious CRNs, the output species is never a reactant. Output-oblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function f:ℕ^d → ℕ is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and output-oblivious.

Cite As Get BibTex

Hooman Hashemi, Ben Chugg, and Anne Condon. Composable Computation in Leaderless, Discrete Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DNA.2020.3

Author Details

Hooman Hashemi
  • The University of British Columbia, Vancouver, Canada
Ben Chugg
  • Stanford University, CA, USA
Anne Condon
  • The University of British Columbia, Vancouver, Canada

Funding

  • Hashemi, Hooman: Supported by an NSERC Discovery Grant.
  • Chugg, Ben: Supported by an NSERC Undergraduate Research Award.
  • Condon, Anne: Supported by an NSERC Discovery Grant.

Acknowledgements

This work benefited greatly from conversations with Eric Severson and David Doty. Thanks also to David Haley and Eric Severson for help in generating the figures.

References

  1. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2221-2239. SIAM, 2018. Google Scholar
  2. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292-299, New York, NY, USA, 2006. ACM Press. URL: https://doi.org/10.1145/1146381.1146425.
  3. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  4. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  5. Stefan Badelt, Seung Woo Shin, Robert F. Johnson, Qing Dong, Chris Thachuk, and Erik Winfree. A general-purpose CRN-to-DSD compiler with formal verification, optimization, and simulation capabilities. In Robert Brijder and Lulu Qian, editors, DNA Computing and Molecular Programming, pages 232-248, Cham, 2017. Springer International Publishing. Google Scholar
  6. Cameron Chalk, Niels Kornerup, Wyatt Reeves, and David Soloveichik. Composable rate-independent computation in continuous chemical reaction networks. In Milan Ceska and David Safránek, editors, Computational Methods in Systems Biology, pages 256-273, Cham, 2018. Springer International Publishing. Google Scholar
  7. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517-534, December 2014. Google Scholar
  8. Ho-Lin Chen, David Doty, and David Soloveichik. Rate-independent computation in continuous chemical reaction networks. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, pages 313-326, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2554797.2554827.
  9. Ben Chugg, Hooman Hashemi, and Anne Condon. Output-oblivious stochastic chemical reaction networks. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, editors, 22nd International Conference on Principles of Distributed Systems, OPODIS 2018, December 17-19, 2018, Hong Kong, China, volume 125 of LIPIcs, pages 21:1-21:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.21.
  10. Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. Algorithmic Bioprocesses, pages 543-584, 2009. Google Scholar
  11. David Doty and Monir Hajiaghayi. Leaderless deterministic chemical reaction networks. Natural Computing, 14(2):213-223, 2015. Google Scholar
  12. Leszek Gąsieniec and Grzegorz Staehowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2653-2667. SIAM, 2018. Google Scholar
  13. G Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 3(2):326–336, 1952. Google Scholar
  14. Adrian Kosowski and Przemysław Uznański. Population protocols are fast. arXiv preprint arXiv:1802.06872, 2018. Google Scholar
  15. Lulu Qian and Erik Winfree. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 332(6034):1196-1201, 2011. Google Scholar
  16. Eric E. Severson, David Haley, and David Doty. Composable computation in discrete chemical reaction networks. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 14-23. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331615.
  17. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7, 2008. Google Scholar
  18. David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences, 107(12):5393-5398, 2010. Google Scholar
  19. David Zhang and Georg Seelig. Dynamic DNA nanotechnology using strand-displacement reactions. Nature chemistry, 3:103-13, February 2011. URL: https://doi.org/10.1038/nchem.957.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact