Composable computation in discrete chemical reaction networks

02/26/2019
by   Eric Severson, et al.
0

We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions f:N^d →N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, having appeared in several earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN. Our main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that f is eventually the minimum of a finite number of nondecreasing quilt-affine functions: essentially "nearly affine" functions, with a fixed (rational) linear slope and periodic offsets.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset