2026-08-19T09:13:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12956 2024-03-06T10:51:10Z ddc:004 open_access

Composable Computation in Leaderless, Discrete Chemical Reaction Networks Hashemi, Hooman Chugg, Ben Condon, Anne Chemical Reaction Networks Stable Function Computation Output-Oblivious Output-Monotonic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hooman Hashemi and Ben Chugg and Anne Condon 2020 Is Part Of LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DNA.2020.3 urn:nbn:de:0030-drops-129560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.3 eng https://creativecommons.org/licenses/by/3.0/legalcode