Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Hashemi, Hooman
Master of Science - MSc
University of British Columbia
This thesis provides a sufficiency condition for the functions f: ℕ² → ℕ which are stably computable by output-oblivious Stochastic Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never reactants. While it is known that precisely the semilinear functions are stably computable by CRNs, such CRNs sometimes rely on initially producing too many output species, and then consuming the excess in order to reach a correct stable state. These CRNs may be difficult to integrate into larger systems: if the output of a CRN C becomes the input to a downstream CRN C′, then C′ could inadvertently consume too many outputs before C stabilizes. If, on the other hand, C is output-oblivious then C′ may consume C’s output as soon as it is available. In this work, we prove that a semilinear function f: ℕ² → ℕ is stably computable by an output-oblivious CRN with a leader if it is both increasing and either grid-affine (intuitively, its domains are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions behaving like the min function). This result complements the necessity condition obtained and proven by other contributors. The run-time analysis provided in the end adds more detail to the proof and the construction.
Sufficiency Condition forOutput-Oblivious Chemical ReactionNetworksand Run-time AnalysisbyHooman HashemiB.Sc., Sharif University of Technology, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)November 2019© Hooman Hashemi, 2019The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Sufficiency Condition for Output-Oblivious Chemical Reaction Networksand Run-time Analysissubmited by Hooman Hashemi in partial fulfillment of the requirements forthe degree of Master of Sciencein Computer ScienceExamining Committee:Anne Condon, Computer ScienceSupervisorJim Little, Computer ScienceSupervisory Committee MemberiiAbstractThis thesis provides a sufficiency condition for the functions f : N2 → Nwhich are stably computable by output-oblivious Stochastic Chemical Reac-tion Networks (CRNs), i.e., systems of reactions in which output species arenever reactants. While it is known that precisely the semilinear functionsare stably computable by CRNs, such CRNs sometimes rely on initially pro-ducing too many output species, and then consuming the excess in order toreach a correct stable state. These CRNs may be difficult to integrate intolarger systems: if the output of a CRN C becomes the input to a downstreamCRN C′, then C′ could inadvertently consume too many outputs before Cstabilizes. If, on the other hand, C is output-oblivious then C′ may consumeC’s output as soon as it is available. In this work we prove that a semilinearfunction f : N2 → N is stably computable by an output-oblivious CRN witha leader if it is both increasing and either grid-affine (intuitively, its domainsare congruence classes), or the minimum of a finite set of fissure functions(intuitively, functions behaving like the min function).This result complements the necessity condition obtained and proven byother contributors.The run-time analysis provided in the end adds more detail to the proof andthe construction.iiiLay SummaryPrinciples of computation are relevant not only for today’s silicon-basedcomputers, but also for programming molecules to compute in novel waysthat are not found in nature. Chemical reaction networks have tradition-ally been used to study extant chemical systems, but are also now beingharnessed to describe molecular programs that compute mathematical func-tions. A desirable property of such programs is that they be composable,that is, the output of one chemical program serves as the input to a secondprogram. In this thesis we contribute to knowledge about what functionscan be stably computed in a composable way by chemical reaction networks.Chemical reaction networks are in definition close to population protocolswhich are another model that is used for distributed computation. Popula-tion protocols model parallel systems that each agent has a state and thestates change by interaction between agents. Because of the similarity ourresults may be also applicable here.ivPrefaceThe research conducted in this article and the problem specified here weredefined by professor Anne Condon and the student Ben Chugg.I was one of the main contributors to the solution of the larger researchproblem. All content provided in the main chapters of this article was solvedsolely by me (that is excluding introduction and related work).The research presented in this thesis has led to the following publication.In this publication I have acted as a coauthor, providing assistance andcontributing to the final proof.• Ben Chugg, Hooman Hashemi, and Anne Condon, 22nd InternationalConference on Principles of Distributed Systems, Conference on Prin-ciples of Distributed Systems (OPODIS 2018)Appears in the proceeding as: “Output-Oblivious Stochastic ChemicalReaction Networks”For this publication I proved the sufficiency condition, and come up withthe structure called semiaffine functions which helped to connect the twosides of the proof.Most of the writing in the paper was done by the other two coauthors.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.1 Chemical Reaction Networks (CRNs) . . . . . . . . . 72.1.2 Linear and Semilinear Sets; Lines, Grids, and Wedges 82.1.3 Semilinear, Semiaffine, Grid-Affine, and Fissure Func-tions . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 A Summary of the Necessity Proof for Theorem 1 . . . . . . 112.2.1 Impossibility Lemmas . . . . . . . . . . . . . . . . . . 112.2.2 General Outline of the Necessity Proof . . . . . . . . 122.3 The General Case . . . . . . . . . . . . . . . . . . . . . . . . 123 Sufficiency Condition for Stable Computability by Output-Oblivious CRNs . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1 Semiaffine Functions . . . . . . . . . . . . . . . . . . . . . . . 143.1.1 Semilinear Functions are Semiaffine . . . . . . . . . . 143.2 Construction of Fissure Functions . . . . . . . . . . . . . . . 17vi3.2.1 Proof of Claim 3 . . . . . . . . . . . . . . . . . . . . . 213.3 Stitching Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 233.4 Final Condition . . . . . . . . . . . . . . . . . . . . . . . . . 253.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.5.1 Example for Claim 3 . . . . . . . . . . . . . . . . . . 253.5.2 Example for Lemma 9 . . . . . . . . . . . . . . . . . . 274 Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.1 The Kinetic Model and Basics . . . . . . . . . . . . . . . . . 314.2 Output Oblivious CRN Time Analysis . . . . . . . . . . . . . 334.2.1 Basics with Leader . . . . . . . . . . . . . . . . . . . 334.2.2 Output Oblivious CRN . . . . . . . . . . . . . . . . . 34Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Appendix: Proofs of LemmasA.1 Proof of Lemma 11 . . . . . . . . . . . . . . . . . . . . . . . 40viiList of Figures1.1 Here we represent a grid-affine function f : N2 → N by itsdecomposition on different domains, all of which are grids.The domains of f are illustrated on the left. Each black pointis a zero-dimensional grid, while the grey points represent fourone-dimensional grids, namely the lines {( ; 0) + (2; i) : ∈N} and {(0; ) + (i; 2) : ∈ N} for i [ 0; 1. The blue pointsrepresent points (n); n2) such that n) + n2 is even, and coverthe union of two grids: {(2 ); 2 2) : t ∈ N} ∪ {(2 ); 2 2) +(1; 1) : t ∈ N}. Similarly, the gold points represent two grids. 31.2 A simple fissure function f : N2 → N. On Figure 1.2a thethree domains of f are illustrated. There is one “fissure line”called Dom(, and two “wedge” domains called DomL andDomB (“A” is above and “B” is below the fissure line). Thefunction value on each of these domains is specified in Fig-ure 1.2b. The function f agrees with the function min{n) +1; n2 + 1} except that it dips down by 1 on the fissure lineDom(. In Figure 1.2c is a CRN which stably computes f . Inthe CRN, the input n [ (n); n2) is represented as counts ofspecies m) and m2 and the leader is initially [0]. The threepossible states [0]; [V] and [B] of the leader track whether theinput lies on the fissure line Dom(, which is the line where<L(n)−<B(n) [ 0, or whether the input lies above or belowthe fissure line, i.e., in domains DomL or DomB respectively.In this simple example, the CRN need not track how far above(or how far below) the fissure line an input might be, sincethe function <L does not depend on n2 (and the function <Bdoes not depend on n)). . . . . . . . . . . . . . . . . . . . . . 53.1 An example of a wedge domain. . . . . . . . . . . . . . . . . . 153.2 A fissure function: A contour plot for an example fissure func-tion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28viii3.3 Nonnegative deficit: Example for Claim 3. . . . . . . . . . . . 293.4 Semiaffine functions: Example for semilinear to semiaffineconversion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30ixAcknowledgementsI would like to take this opportunity to acknowledge and express my sin-cere gratitude toward my research supervisor professor Anne Condon, forher constant support, unparalleled kindness and consistent guidance. Hersupport exceeded expectation and I’m really thankful for this.I want to thank professor Jim Little, for supervising my program. Hehelped me and guided me through my studies. He supported me to enter asecond field of study and helped me to gain experience.Finally special thanks to my family for their patience during my program.Without their support I would have not been able to be where I am today.xDedicationTo my family,for their constant love and support.xiChapter 1IntroductionStochastic Chemical Reaction Networks (CRNs)—systems of reactions in-volving chemical species—have traditionally been used to reason about ex-tant physical systems, but are currently also of strong interest as a dis-tributed computing model for describing molecular programs [8, 20]. Theyare closely related to Population Protocols [1, 3, 4, 10], another distributedcomputing model; these models have found applications in areas as diverseas signal processing [16], graphical models [17], neural networks [15], andmodeling cellular processes [5, 6]. CRNs can simulate Universal Turing Ma-chines [2, 20]. However, these simulations have drawbacks: the number ofreactions or molecules may scale with the space usage and the computationis only correct with an arbitrarily small probability of error. If we requirestable computation—that the CRN always eventually produces the correctanswer—then Angluin et al. [4] showed that precisely the class of semilinearpredicates can be stably computed. Chen et al. [8] extended this result toshow that precisely the semilinear functions can be stably computed.Recent advances in physical implementations of CRNs and, more gener-ally, chemical computation using strand displacement systems (e.g., [18, 21–23]) are a step towards the use of CRNs in biological environments and nan-otechnology. As these systems become more complex, it may be necessaryto integrate multiple, interacting CRNs in one system. However, currentCRN constructions may perform poorly in such scenarios. As a concreteexample, consider a CRN C given by the reactions m → 2n , n + a → ∅,where the system begins with n copies of input species m, and one copyof a (called the leader). This CRN eventually produces 2n − 1 copies ofoutput species n , and so (stably) computes the function n 7→ 2n − 1. Ifanother CRN C′ uses the output of C as its input, and if the first reactionoccurs n times before the second occurs at all, then C′ may consume all2n copies of n and may thus itself produce an erroneous output. CurrentCRN constructions circumvent this issue by using diff-representation, wherethe count y of output species n of a CRN is represented indirectly as thedifference y [ yP − yN between the counts of two species n P and n N [8],rather than as the count of one output species n . While these constructions1enable the counts of both n N and n P to be non-decreasing throughout thecomputation, it is not immediately clear how a second CRN might use thesetwo species reliably as input.More generally, if multiple function-computing CRNs comprise a largersystem it can be desirable that no CRN ever produces a number of out-puts that exceeds its function value. We might even demand more: that anoutput species of a CRN is never used as a reactant species, i.e., is never con-sumed. This ensures that any secondary CRN relying on the first’s outputcan consume the output indiscriminately.It is thus natural to ask: What functions can be stably computed inan output-oblivious manner, in which outputs are never reactants, withoutusing diff-representation?This question is the focus of this work. Doty and Hajiaghayi [13] alreadyobserved that output-oblivious functions must not only be semilinear butalso increasing, that is, f(n)) ≤ f(n2) whenever n) ≤ n2, but did notprovide further insights. Chalk et al. [7] asked the same question but for adifferent model, namely mass-action CRNs. That model tracks real-valuedspecies concentrations, unlike the stochastic model in which configurationsare vectors of species counts. In contrast with the mass-action mode, leadermolecules can play a very important role in the stochastic model, and wefocus on the case where leaders are present. Mass-action CRNmodels cannothave leaders since there are no species counts. Functions that are stablycomputable by output-oblivious mass-action CRNs must be super-additive[7], that is f(n) + f(n′) ≤ f(n + n′). Semilinear functions that are super-additive are a proper subset of the class of output-oblivious functions thatcan be stably computed by stochastic CRNs with leaders.1.1 Our ResultsIn this work we present the sufficiency condition for a characterization ofclass of output-oblivious semilinear functions, i.e., those functions that canbe stably computed by an output-oblivious stochastic CRN. We assume thatone copy of a leader species is present initially in addition to the input. Wefocus on functions with two inputs and one output, since this case already isquite complex. Our results generalize trivially when there are more outputssince each output can be handled independently, and we believe that ourtechniques also generalize to multiple inputs.Later Severson et al. [19] characterized the functions with more thantwo inputs that can be stably computed in an output-oblivious manner.2f(n) [8>>>><>>>>:<)(n) [ 2; n ∈ Dom);<2(n) [ n) + n2; n ∈ Dom2;<+(n) [ n) + 2n2 + 5; n ∈ Dom+;<4(n) [ n) + 2n2 + 4; n ∈ Dom4 OFigure 1.1: Here we represent a grid-affine function f : N2 → N by itsdecomposition on different domains, all of which are grids. The domains off are illustrated on the left. Each black point is a zero-dimensional grid,while the grey points represent four one-dimensional grids, namely the lines{( ; 0) + (2; i) : ∈ N} and {(0; ) + (i; 2) : ∈ N} for i [ 0; 1. The bluepoints represent points (n); n2) such that n) + n2 is even, and cover theunion of two grids: {(2 ); 2 2) : t ∈ N} ∪ {(2 ); 2 2) + (1; 1) : t ∈ N}.Similarly, the gold points represent two grids.Their results follow a simpler path; They do not use the notation of fissurefunctions which we will introduce later.Our results also hold for Population Protocols, since stable function-computing CRNs can be translated into Population Protocols and vice versa.Section 2.1 introduces the relevant background in order to formally describeour results, but we describe them informally here.Perhaps the simplest type of output-oblivious function with domain N2is an affine function, such as f(n); n2) [ 2n) + 3n2 + 1 which could becomputed by a CRN with reactions a→ n , m) → 2n and m2 → 3n wherea is a single leader. Here and hereafter, mt will typically correspond to theinput species representing nt.In Chapter 3 we show that an increasing function that can be specifiedas partial affine functions whose domains are different “grids” of N2 is alsooutput-oblivious; for example, the function f(n); n2) [ 2n) + 3n2 + 1 whenn) + n2 [ 0 mod 2, and f(n); n2) [ 2n) + 3n2 when n) + n2 [ 1 mod 2.More generally, a function that can be specified in terms of output-obliviouspartial functions ft, 1 ≤ i ≤ k, defined on different grids of N2, is output-oblivious. The grids may be 0-dimensional, in which case they are points;1-dimensional in which case they are lines, or 2-dimensional. We call suchfunctions grid-affine functions. See Figure 1.1 for a slightly more compli-cated example of a grid-affine function, and a representation of its domains.We show how the CRNs for partial functions ft on the different grids canbe “stitched” together to obtain an output-oblivious CRN for f .It is also straightforward to obtain an output-oblivious CRN for a func-3tion f that is the min of a finite set of output-oblivious functions. In thesimplest case, for example, min(n); n2) can be computed as m) +m2 → n .In our main positive result we describe a more general type of “min-like”function, which we call a fissure function, and we show how to constructoutput-oblivious CRNs for such functions. We give a very simple exampleof a fissure function and a corresponding output-oblivious CRN in Figure1.2.However, constructing CRNs for other fissure functions appears to besignificantly trickier than that shown in Figure 1.2. Consider the functionf(n); n2) [ 2n) + 3n2 + 2 if n) S n2, f(n); n2) [ 3n) + 2n2 + 2 if n) < n2and f(n); n2) [ 5n) on the “fissure line” n) [ n2. The simple line-trackingmechanism of the CRN of Figure 1.2 can’t be used here because the affinefunctions for the “wedge” domains “n) S n2” and “n) < n2” depend both onn) and n2. Also the function cannot be written as the sum of an increasinggrid-affine function and an increasing simple fissure function of the type inFigure 1.2, where the “above” function <L() depends only on n) and the“below” function <B() depends only on n2. Our main positive result and thefocus of this thesis is a construction that can handle such fissure functions,as well as functions with multiple parallel fissure lines.In Section 2.2 we briefly present results on the negative side obtained bythe other authors. A non-trivial example of a function that is not output-oblivious is the maximum function. Intuitively, a CRN that attempts tocompute the max would have to keep track of the relative difference of itstwo inputs in order to know when the count of one input overtakes thecount of the other, and it’s not possible to keep track of that difference witha finite number of states. Developing this intuition further, we show thatan increasing semilinear function f : N2 → N is output-oblivious if and onlyif f is grid-affine or is the min of finitely many fissure functions.Putting both positive and negative results together, I state the mainresult jointly obtained with other authors here (see Section 2.1 for precisedefinitions of grid-affine and fissure functions).Theorem 1. A semilinear function f : N2 → N is output-oblivious if andonly if f is increasing and is either grid-affine or the minimum of finitelymany fissure functions.Since only semilinear functions are stably computable by CRNs, Theo-rem 1 provides a complete characterization of functions f : N2 → N whichare output-oblivious. A function is output-monotonic if it is stably com-putable by a CRN whose output count never decreases but unlike an output-4(a)f(n) [8><>:<L(n) [ n) + 1; n ∈ DomL;<((n) [ n); n ∈ Dom(;<B(n) [ n2 + 1; n ∈ DomB O(b)[0] +m) → [V] + n[0] +m2 → [B] + n[V] +m2 → [0][B] +m) → [0](c)Figure 1.2: A simple fissure function f : N2 → N. On Figure 1.2a the threedomains of f are illustrated. There is one “fissure line” called Dom(, and two“wedge” domains called DomL and DomB (“A” is above and “B” is belowthe fissure line). The function value on each of these domains is specified inFigure 1.2b. The function f agrees with the function min{n) + 1; n2 + 1}except that it dips down by 1 on the fissure line Dom(. In Figure 1.2c isa CRN which stably computes f . In the CRN, the input n [ (n); n2) isrepresented as counts of speciesm) andm2 and the leader is initially [0]. Thethree possible states [0]; [V] and [B] of the leader track whether the inputlies on the fissure line Dom(, which is the line where <L(n)−<B(n) [ 0, orwhether the input lies above or below the fissure line, i.e., in domains DomLor DomB respectively. In this simple example, the CRN need not track howfar above (or how far below) the fissure line an input might be, since thefunction <L does not depend on n2 (and the function <B does not dependon n)).5oblivious CRN an output may act as a catalyst of a reaction, being both areactant and product. For example, the CRN m → n , a+ n → 2n whichcomputes the function n 7→ n+1 for n ≥ 1 and 0 7→ 0 is output-monotonic,but not output-oblivious. Thus, we also obtain a characterization for output-monotonic functions.To obtain our results, we provide new characterizations of semilinearsets and functions. We show that all semilinear sets can be written as finiteunions of sets which are the intersection of grids and hyperplanes. Such setsare points, lines or wedges (pie-shaped slices) on 2D grids. Using this and therepresentation of semilinear functions as piecewise affine functions discoveredby Chen et al. [8], we give a new representation of semilinear functions as“periodic semiaffine functions”, essentially piecewise affine functions whosedomains are points, lines or wedges.The rest of the thesis is structured as follows. Section 2.1 provides therelevant technical background on CRNs, stable computation and semilinearfunctions. It also contains our new results on the structure of semilinearsets and functions, and rigorous definitions of grid-affine and fissure func-tions. In the next section and chapter we prove Theorem 1, with Section2.2 giving a general outline that any function which is stably computable byan output-oblivious CRN obeys certain properties and Chapter 3 providingexplicit constructions of CRNs. Finally in Chapter 4 an analysis of the timecomplexity of functions computable by output-oblivious CRNs is provided.6Chapter 2Related Work2.1 PreliminariesWe begin by introducing Chemical Reaction Networks, and what it meansfor a CRN to stably compute a function. We then formally define grid-affine and fissure functions and, along the way, state new results concerningsemilinear sets and functions.2.1.1 Chemical Reaction Networks (CRNs)CRNs specify possible behaviors of systems of interacting species. LetZ [ {o); O O O ; ox} be a finite set of species. At any given instant, thesystem is described by a configuration c ∈ NZ , where x(ot) is the cur-rent count of the species ot ∈ Z in the system. The system’s configu-ration changes by way of reactions, each of which is described as a pair(s; t) [ ((s); O O O ; sx); (t); O O O ; tx)) ∈ NZ × NZ such that for at least one1 ≤ j ≤ m, sj ̸[ tj . Reaction (s; t) can be written as∑v2sk>(svov →∑v2tk>(tvovOThe species ov with sv S 0 are the reactants, which are consumed, whilethose with tv S 0 are the products (if both sv S 0 and tv S 0 then speciesov is a catalyst). A CRN is thus formally described as a pair C [ (Z;R),where Z is a set of species, and R a set of reactions. Reaction r [ (s; t) isapplicable to configuration c if s ≤ c (pointwise inequality), i.e., sufficientlymany copies of each reactant are present. If applicable reaction (s; t) occurswhen the system is in configuration c [ (x); O O O ; xx), the new configurationis c′ [ (x)− s)+ t); O O O ; xx− sx+ tx). In this case we say that c′ is directlyreachable from c and write c r−→ c′. An execution E [ c(; O O O ; ct of C is asequence of configurations of C such that ct is directly reachable from ct−)for 1 ≤ i ≤ t. We say that ct is reachable from c(.7Stable CRN Computation of Functions with a Leader. Angluin etal. [3] introduced the concept of stable computation of boolean predicatesby population protocols, and Chen et al. [8] adapted the notion to func-tion computation by CRNs. While this work focuses on two-dimensionaldomains, we present the following details in full generality.Let f : Nv → Nk be a function. Formally, a Chemical Reaction Network(CRN) for computing f with a leader is C [ (Z;R; I;O; a), where Z is a setof species, R is a set of reactions, I [ {m); m2; O O O ; mv} ⊆ Z is an orderedset of input species, O [ {n); n2; O O O ; nk} ⊆ Z is an ordered set of outputspecies and a is a leader species, a ∈ Z \ I.Function computation on input n [ (n); O O O ; nv) ∈ Nv starts from a validinitial configuration c( of C; namely a configuration in which the count ofa is 1, the count of species mt is nt, and the count of any other speciesis 0. A computation is an execution of C from a valid initial configurationto a stable configuration. A configuration x is stable if for every c′ ∈ Nxreachable from c, c(n ) [ c′(n ) for all n ∈ O. That is, once the systemreaches configuration c, the counts of the output species do not change. Wesay that C stably computes f if for every valid initial configuration c( and forevery configuration c reachable from c(, there exists a stable configurationc′ reachable from c such that f(c((m)); O O O ; c((mv)) [ (c′(n)); O O O ; c′(nk)).Output-monotonic and Output-oblivious CRNs. We say a CRN C isoutput-oblivious if it never consumes any of its output species, and output-monotonic if on all executions from a valid initial configuration, the countof any output species never decreases. As noted in the introduction, thesenotions are not equivalent. We say a function f is output-oblivious (mono-tonic) if there exists an output-oblivious (monotonic) CRN which stablycomputes f . Our results show that the set of output-oblivious functionsand output-monotonic functions are the same.2.1.2 Linear and Semilinear Sets; Lines, Grids, and WedgesFor a vector v, let vt denote its ith coordinate. Let Y ⊆ N2 and let #)and #2 denote the projection maps onto x and y axes, respectively. We sayY is two-way-infinite if |#)(Y)| [ |#2(Y)| [ ∞, one-way-infinite if either|#)(Y)| [ ∞ or |#2(Y)| [ ∞ but not both, and finite if |#)(Y)| <∞ and|#2(Y)| < ∞. Also, if V;B ⊆ N2 and n ∈ N2 we let V + B [ {v + b : v ∈V; b ∈ B} and V+ n [ V+ {n}.A set Z ⊂ N2 is linear if Z [ {∑tt=) xt t + o : t ∈ N} for some t ∈ Nand xt;o ∈ N2. If t [ 1 we say that Z is a line. A set is semilinear if it is8the finite union of linear sets.A linear set G ⊆ N2 is a grid if there exist p; q ∈ N and o ∈ N2 such thatG [ {(p; 0) ) + (0; q) 2 : t ∈ N} + o [ {(p ) + o); q 2 + o2) : t ∈ N}. Ifboth p and q are zero, the grid is simply the point o. If p S 0 and q [ 0,or p [ 0 and q S 0, the grid is a one-way-infinite line with period p or qrespectively. If p [ q S 0 we say that the grid is periodic, with period p. Welet Gp + o be the grid {( )p; 2p) : t ∈ N}+ o and write Gp if o [ (0; 0).A threshold set is a semilinear set with the form {n : n · v ≥ r} (i.e., ahalfspace) for some v ∈ Z2 and r ∈ Z [4]. Let Z be a two-way-infinite linearset of the form G∩T , where G is a grid and T is a finite intersection of thresh-old sets. Z is bounded by two lines (represented by threshold sets and/orlines parallel to the x or y axes; the points on these lines, if any, are in Z).(Note that the boundary of a threshold set {n : (n); n2) ·(v); v2) ≥ r} can bewritten as the linear set {(v2=k;−v)=k) + (|min{0; r=v2}|;max{0; r=v)}) : ∈ N; k [ gcd(v); v2)} or similarly if it does not pass any points on theaxes. For example, 〈n); n2〉 · 〈−3; 2〉 [ −1 is the set (2; 3) + (1; 0). If a lineis infinite then (v2;−v)) ≥ (0; 0).) If the two bounding lines are parallel,Z is the finite union of lines on G, i.e., all points of each line lie on grid G.Otherwise we call Z a wedge on G. For example, the sets {n : n) ≥ n2} and{(1; 1) ) + (1; 2) 2 : t ∈ N} are wedges on G). Likewise, the two regionsabove and below the fissure line in Figure 1.2 are wedges on G). More gen-erally, we can intuitively think of a wedge as a pie-like slice of N2∩G, exceptthat pieces may be chopped off near the narrow “corner” that is closest tothe origin. If the two bounding lines are the x and y axes, the wedge isall of G. We can show the following characterization of semilinear sets; seeSection 3.1.1 for the proof and a more formal definition of a wedge.Lemma 1. Every semilinear set can be represented as the finite union ofpoints, lines on grids, and wedges on grids, with all grids having the sameperiod.2.1.3 Semilinear, Semiaffine, Grid-Affine, and FissureFunctionsFor a function f : N2 → N, the restriction of f to domain Y ⊆ N2 is thepartial function f |D : Y → N given by f |D(n) [ f(n) for all n ∈ Y. We saythat f : Y → N is (partial) affine if f(n) [ v)n) + v2n2 + v( for rationalnumbers v(; v), and v2 ∈ Q. Function f is a finite combination of the finiteset of functions {<); O O O ; <v} if Dom(f) [∪vt=)Dom(<t) and f(n) [ <t(n)whenever n ∈ Dom(<t). Throughout we write Domt in place of Dom(<t).We define semilinear functions using a characterization of Chen et al. [8]:9Definition 1 (Semilinear function [8]). A function f : N2 → N is semilinearif and only if f is a finite combination of partial affine functions with lineardomains.We next define semiaffine functions, a refinement of Definition 1. Lemma2 then states that semilinear and semiaffine functions are equivalent. Theproof is in Section 3.1.1.Definition 2 (Semiaffine function). Let Gp+o be a periodic grid. A functionf : Gp+o→ N is semiaffine if and only if f is a finite combination of partialaffine functions whose domains are points, lines or wedges on grid Gp + o.A function f : N2 → N is semiaffine with period p ∈ N+ if and only if f isa combination of semiaffine functions on grids of the form Gp + o.Lemma 2. A function f : N2 → N is semilinear if and only if f is semiaffine.Our main result, Theorem 1, shows that output-oblivious functions areexactly the following two special types of semiaffine functions. In the firstspecial case, on each grid Gp+ o, f is restricted to be an affine (rather thana more general semiaffine) function.Definition 3 (Grid-affine function). A function f : N2 → N is grid-affineif and only if for some p ∈ N+, f is a combination of affine functions onpoints and on grids of period p.A function f : Y → N is increasing if f(n) ≤ f(n′) for all n ≤ n′, wheren;n′ ∈ Y. Doty and Hajiaghayi [13] observed that an output-obliviousfunction must be increasing. We hereafter focus on increasing functions.Definition 4 (Fissure function). Let G be a two-way-infinite grid. Anincreasing semiaffine function f : G → N is a partial fissure function if forsome o ∈ N2, f can be represented as follows for all n ≥ o:f(n) [8>>>><>>>>:<L(n); if <L(n)− <B(n) ≤ −k;<−t(n) [ <L(n)− y−t; if <L(n)− <B(n) [ −i; 1 ≤ i < k;<t(n) [ <B(n)− yt; if <L(n)− <B(n) [ i; 0 ≤ i < k;<B(n); if <L(n)− <B(n) ≥ kO(2.1)where <L(n) [ V(+V)n)+V2n2, <B(n) [ B(+B)n)+B2n2, for integers V(and B(, nonnegative rationals V); V2; B) and B2, and nonnegative integersy−v; O O O ; y−); y(; y); O O O ; yv. For −k ≤ i ≤ k, we refer to the line <L(n) −<B(n) [ i as a fissure line and call it at. Moreover, <L < <B on DomL and10<B < <L on DomB; thus V) S B) and B2 S V2. We say f : N2 → N is a(complete) fissure function if f is a combination of partial fissure functionson grids of period p.2.2 A Summary of the Necessity Proof forTheorem 1Here I summarize the necessity proof that, if a function is output-monotonic,then it is either grid-affine or the minimum of finitely many fissure functions.The proof of this direction was obtained by my co-authors with small con-tributions from me. For details of the proofs, see Chugg et al. [9]. FirstI describe two conditions on a function which ensure that it is not output-oblivious. Then I explain the general idea of the necessity proof.2.2.1 Impossibility LemmasLemma 3. Let f : N2 → N be a semiaffine function. Suppose that f [ <ton Domt and f [ <j on Domj, where Domt and Domj lie on the same grid,Domt is a wedge domain and for some two-way-infinite line a in Domj,<j S <t on a. Then f cannot be stably computed by an output-monotonicCRN.Lemma 4. Let f : N2 → N be a semiaffine function. Suppose that f [ <ton Domt and f [ <j on Domj, where Domt and Domj are wedge domainson the same grid G such that (i) <t [ <j on N2 and (ii) there is a two-way-infinite line a ⊂ G separating Domt and Domj, with <L < <t ([ <j) on a.Then f cannot be stably computed by an output-monotonic CRN.The general idea of these two lemmas is to find a configuration thatallows all possible reaction sequences of another configuration for any sameamount of remaining inputs. And then find a set of remaining inputs anda reaction sequence of the later configuration that outputs more than theanswer in the former configuration. To find such two configurations it isenough to find two settings such that the count of all species in one settingis greater than the other. To find a reaction sequence that causes a problem,it is enough to limit the search of the two increasing settings to pairs that cancause problems. An infinite sequences of such pairs exists in the functionsmentioned in the lemmas and by some property of infinite sequences [11] aninfinite sequence of configurations has an increasing subsequence.112.2.2 General Outline of the Necessity ProofThe proof analyzes each grid of the semiaffine function separately. For alarge enough offset o the threshold lines divide the points larger than oto wedge domains and line domains sorted by threshold line slopes. Thewedges and lines adjacent to each set of parallel lines can define partialfissure functions because of the two impossibility lemma. The minimum ofthese fissure functions is equal to f on all of these domains.2.3 The General CaseAs mentioned in the results section, Severson et al. [19] characterized thefunctions with more than two inputs that can be stably computed in anoutput-oblivious manner. They do not use the notation of fissure functions.Instead, they express output-oblivious functions for large enough inputs asminimum of grid-affine functions (or more accurately minimum of quilt-affine functions within different infinite domains). The main idea of theirapproach is that with large enough periods of grid-affine functions, the pe-riods will be larger than fissure widths and the anomalies of fissure linescan be considered as periodic characteristics of a grid-affine function. Bythis assumption all output-oblivious functions can be expressed as minimumof grid-affine functions where each fissure and each wedge is defined by aseparate grid-affine function. For example for the fissure function in thefigure 1.2 the minimum of the following increasing grid-affine functions willresult in the desired fissure function,f)(n) [ n) + 1;f2(n) [{n12 +n22 ; n) [ n2 mod 2;n12 +n22 +)2 ; n) ̸[ n2 mod 2;f+(n) [ n2 + 1OA simple CRN can be constructed for each of these functions and the mini-mum can be calculated with a simple operation.For the inputs with more than two dimensions, their solution is recursive.That is by fixing any number of inputs to constants, for large enough valuesof the other input variables the function is minimum of grid-affine functions.One of the advantages of this approach to the fissure function approach isthat fissure functions are not as well defined as the minimum of grid-affine12functions in higher dimensions. For example a higher dimensional fissurefunction can have a fissure of complex shape (that is the cross sections offissures are 2D in a 3D space and can be any 2D shape) or even may havean infinite number of fissure lines in one direction (The 2D cross section ofthe fissure can be infinite in one direction).13Chapter 3Sufficiency Condition forStable Computability byOutput-Oblivious CRNsThis section shows that if an increasing semilinear function f : N2 → N iseither a grid-affine function or a fissure function, then f is output-oblivious.We do this in three lemmas. Lemma 10 shows that an increasing affinefunction whose domain is a grid is output-oblivious. Lemma 12 shows thata partial fissure function is output-oblivious. Finally, Lemma 13 shows thatif f is increasing and is a combination of partial output-oblivious functionsdefined on grids, we can stitch together the CRNs for the partial functionsto obtain an output-oblivious CRN for f .3.1 Semiaffine FunctionsSemiaffine functions as defined in the preliminaries chapter help to breakdown the semilinear functions with periodic structures into a set of non-periodic functions defined all over certain grids. This helps both the con-struction of CRNs for such functions by first constructing the non-periodicfunctions and then combining the CRNs to create the original semilinearfunction, and also helps to limit the impossibility arguments in the neces-sity condition to a non-periodic context.3.1.1 Semilinear Functions are SemiaffineThe CRN provided in the next sections is designed for Semiaffine functions.In this section we shortly summarize that the semilinear functions are semi-affine and therefore the CRNs constructed for semiaffine functions also workfor the semilinear functions. For a complete proof see [9].14Figure 3.1: An example of a wedge domain.Proof of Lemma 1Here we prove Lemma 1. To do this, we first prove, via a sequence of lemmas,that every linear set is in fact a finite union of sets of the form G∩T , where Gis a grid and T is a finite intersection of threshold sets, where moreover thegrids have the same period. We use several useful properties of semilinearsets due to Angluin et al. [4].A horizontal threshold set has the form {n : n2 ≥ r} for some r ∈ Z, i.e.,the set includes all the points above the horizontal line n2 [ r. A verticalthreshold set is defined similarly, including all the points to the right of somevertical line. The slope of a threshold set {n : n · v ≥ r} is the slope of theits bounding line {n : n · v [ r}, which is −v)=v2.Definition 5. Let H and k be horizontal and vertical threshold sets, respec-tively. Let iU and iL be threshold sets such that the slope of iU is strictlygreater than that of iL. A set Y ⊂ N2 is a wedge domain if it can be writtenas G ∩ iU ∩ iL ∩H ∩ k for some grid G. See Figure 3.1.A modulo set is a set of the form {n : n ·v ≡ r mod p} for some v ∈ N2,and r; p ∈ N. We call p the period of the set. Recall that a threshold set hasthe form {n : n · v ≥ r} for some v ∈ Z2, r ∈ Z. A boolean combination ofsets refers to a combination of sets by union and intersection. The followinglemma relates semilinear sets to modulo and threshold sets.Lemma 5 ([4]). Every semilinear set can be represented as a finite booleancombination of modulo sets and threshold sets.Next, we make a simple observation concerning the period of grids.Lemma 6. Any grid G [ {(p ); q 2) + (o); o2) : t ∈ N} can be written asa finite union of grids with the same period.Proof. Let k be a multiple of both p and q. For all i; j ∈ N such that pi < k15and qi < k, let ot;j [ (o) + pi; o2 + qi). It is then easily verified thatG [∪t;jGv + ot;j OThe next lemma demonstrates that modulo sets are effectively unionsof grids in hiding. For example, the modulo set b [ {n : 2n) + x2 ≡ 0mod 3} can be written as G+ ∪ G+ + (1; 1) ∪ G+ + (2; 2).Lemma 7 ([9]). Any modulo set can be expressed as the finite union ofgrids.Since the representation of a semilinear set Z may also have intersec-tions of modulo sets (according to Lemma 5) we must be able to write theintersection of modulo sets as grids as well. We do this by first convert-ing the modulo sets into grids as per Lemma 7 and then reasoning aboutthe intersection of grids. The next lemma allows us to write the intersec-tion of these grids as the union of other grids. As an example, considerV [ {( ); 3 2) : t ∈ N} and B [ G2 + (1; 2). Here, V ∩ B is the grid{(2 ); 6 2) + (1; 0) : t ∈ N}.Lemma 8 ([9]). The intersection of two grids can be expressed as the finiteunion of grids.Finally, using distributivity of set operations can prove the main result.Lemma 9. Every semilinear set can be written as a finite union of sets ofthe form G ∩ T , where G is a grid and T is a finite intersection of thresholdsets. Moreover, we may assume that each grid has the same period.Proof. Let a be semilinear. Using Lemma 5 express a as a finite booleancombination of threshold and modulo sets. Expressing each modulo set asa finite union of grids according to Lemma, 7 and then using distributivityof set operations and Lemma 8 we can write a [ ∪Nj=) Gj ∩ T j for somec ∈ N where each T j is a finite intersection of threshold sets and Gj is agrid. Finally, applying Lemma 6, we may assume that each Gj has the sameperiod.It now remains only to remark that we have in fact proven Lemma 1.Proof of Lemma 1. Let a be semilinear and using the previous lemma writea [∪Nj=) Gj ∩ T j . Fix b [ Gj ∩ T j . If b is finite, then it can be writtenas the finite union of points. If T j includes only the boundary of some16threshold set, then b is a line on the grid Gj . Otherwise, b is infiniteand is not a line. It follows that b can be written as the union of a wedgedomain and finitely many points.Proof of Lemma 2. From Definition 1 (Chen et al.), f can be represented bythe partial functions {<); O O O ; <x} where Domt is linear for each i. ApplyingLemma 5 and Lemma 6, we can write Domt as the union of semiaffine setswith the same period, say p. Therefore, each grid of period p is covered by adistinct function ft which is defined by the union of all affine functions whosedomain covers this grid. Thus, it follows that f is a periodic combination ofpartial semiaffine functions on grids.3.2 Construction of Fissure FunctionsLemma 10. Let G be a grid. Any increasing affine function f : G → N isoutput-oblivious.Proof. We consider the case that G [ {(p; 0) ) + (0; q) 2 : t ∈ N} + ois two-way-infinite; the cases when G is a point or a line are simpler. Letf(n) [ v)n) + v2n2 + v(, where v); v2 ∈ Q+ and v( ∈ Q. Since G istwo-way-infinite and f is increasing, v) and v2 are nonnegative. On inputn [ (n); n2) ∈ G, i.e., given n) copies of m) and n2 copies of m2, thefollowing CRN will produce f(n) copies of n :a+ o)m) + o2m2 → a′ + (v)o) + v2o2 + v()n // base casea′ + pm) → a′ + v)pna′ + qm2 → a′ + v2qnNote that the first reaction must produce a non-negative and integral num-ber of n ’s since f(o) ∈ N. Likewise, v)p ∈ N since v)p [ f(o+(p; 0))−f(o),and similarly for v2q. Finally, the CRN is clearly output-oblivious since theoutput species n is never a reactant.We show in Lemma 12 below that any partial fissure function is output-oblivious. First we describe some useful structure pertaining to partial fis-sure functions f : G → N. We can represent such a fissure function asf(n) [ min{<L(n); <B(n)} − yt, where yt is determined by the fissure lineat on which n resides, and yt [ 0 if i is not on a fissure line; this formulationis not identical to but is equivalent to that of Definition 4. As noted in thatdefinition, it must be that V) S B) and B2 S V2, since <L < <B on DomLand vice versa.17For all integers i, let at be the line <L(n) − <B(n) [ i. All of theselines, which include the 2k− 1 “fissure lines” at;−k < i < k, have the sameslope. In addition to the fissure lines, our CRN construction will also referto the lines at for i in the range [k; O O O ;K − 1], where K [ k + ymax − 1.We call these the lower boundary lines, and we call the lines at for i in therange [−K + 1; O O O ;−k] the upper boundary lines. Note that (0; 0) is on theline aL0−B0 and more generally, if point p is on line at then (V) −B))p) −(B2−V2)p2 [ i−V(+B(. For n ∈ G letb(n) [ (<L(n); <B(n)). The nextlemma shows that b(n) ∈ N2 for all sufficiently large n ∈ G, even thoughDomL and DomB are proper subsets of G.Lemma 11. Let < : Y → N be a partial affine function, where Y is a wedgedomain on G. Let m be a minimal point of Y. Then <(n) ∈ N on all n ∈ Gwith n ≥m.We let P be the set of rational points p for which b(p) ∈ N and let Qbe the range ofb with respect to domain P. For q ∈ Q, letb−)(q) denotethe inverse of b (b−)q is unique since (V); V2) and (B); B2) are linearlyindependent). The following claim follows easily from the definition of band will be useful later.Claim 1. Let z); z′); z2; z′2 ∈ N. If z) ≤ z′) and b−)(z); z2) is in DomB thenb−)(z′); z2) is also in DomB. Similarly if z2 ≤ z′2 and b−)(z); z2) is inDomL then b−)(z); z′2) is also in DomL.Lemma 12. Any partial fissure function f : G → N is output-oblivious.Proof. For simplicity we assume that the grid G is N2, i.e., the period ofthe grid is 1 and the offset o is zero; it is straightforward to generalize tolarger grid periods. With these assumptions, it must be that V( and B( arenonnegative integers, which slightly simplifies base cases of our construction.The CRN input is represented as the initial counts of species m) and m2,and x [ (x); x2) denotes the counts of m) and m2 that have been consumedat any time. Rather than producing output f(x) directly upon consumptionof x, our CRN produces <L(x) copies of a species o) and <B(x) copies ofa species o2, effectively computing the mapping b described above. Notethat <L(x) and <B(x) are nonnegative integers by Lemma 11. The CRNworks backwards from the quantities <L(x) and <B(x) to reconstruct f(x).Roughly this is possible because f(x) is “almost” the min of <L(x) and<B(x), and min is easy to compute. More precisely, we can assume that18f(x) [ min{<L(x); <B(x)} − yt, where yt is determined by the fissure lineat on which n resides, and yt [ 0 if i is not on a fissure line. In additionto the input, a leader a is also present initially. Other CRN molecules (notinitially present) represent a state [lx; lz; y] containing three components; weexplain the components later. Our CRN has three types of reactions: o-producing, o-consuming, and n -producing reactions. The first o-producingreaction handles the base case, producing (<L(0; 0); <B(0; 0)) [ (V(; B():a→ a′ +V(o) +B(o2OThe remaining two o-producing reactions consume m) and m2 while pro-ducing o) and o2. If at is the line containing x, the first state component,lx, keeps track of i mod 2K − 1, where K [ k + ymax. If i is in the range[−K +1;K − 1] then lx uniquely determines i. For convenience in what fol-lows, we consider lx to be in the range [−K+1;K−1] rather than [0; 2K−1].The reactions are as follows, where ∗ represents any state component valuethat is unchanged as a result of the reaction:[lx; ∗; ∗] +m) → [lx + (V) −B)) mod 2K − 1; ∗; ∗] +V)o) +B)o2[lx; ∗; ∗] +m2 → [lx + (V2 −B2) mod 2K − 1; ∗; ∗] +V2o) +B2o2We next describe the o-consuming reactions. These reactions updatethe remaining two components of the state to keep track of which fissureor boundary line contains b−)(z), where z [ (z); z2) denotes the countsof (o); o2) that have been consumed at any time. The reactions also trackwhat is the deficit, i.e., the difference between the “true” output f(b−)(z))and the current output y, i.e., number of copies of species n that has beenactually produced so far. Formally, all reactions maintain the following stateinvariant: if after any reaction the state is [lx; lz; y] then1. lz is the index of the boundary or fissure line alz that containsb−)(z),and lz is in the range −K + 1 ≤ lz ≤ K − 1; and2. y [ f(b−)(z))−y is the deficit in the number of y’s produced, and is inthe finite range −ymax ≤ y ≤ 2ymax+1, where ymax [ max{yt | −k <i < k}.o-consuming reactions of the first type handle the base case when n [ (0; 0):a′ +V(o) +B(o2 → [V( −B(; V( −B(;min{V(; B(} − yL0−B0 ]O19o-consuming reactions of the second type consume a copy of o) and reac-tions of the third type consume a copy of o2. Upon consumption, the statecomponents are updated to ensure that the state invariant holds.[lx; lz; y] + o) → [lx; lz + 1; y+ y+lz ]; −K < lz < k; y ≤ ymax and[lx; lz; y] + o2 → [lx; lz − 1; y+ y−lz ]; −k < lz < K; y ≤ ymax;wherey+lz [{ylz − ylz+); lz ≥ 0ylz − ylz+) + 1; lz < 0Oand y−lz [{ylz − ylz−) + 1; lz ≥ 0ylz − ylz−); lz < 0OThe deficit y can never exceed 2ymax + 1 since the reactions are only appli-cable when y ≤ ymax and y can increase by at most ymax + 1.The n -producing reactions produce output molecules of species n , whilemaintaining the state invariant above, and ensuring that at the end of thecomputation the number of n s produced equals f(n). The first n -producingreaction produces y− ymax copies of n when y becomes greater than ymax.[∗; ∗; y]→ [∗; ∗; ymax] + (y− ymax)n; if y S ymaxOBefore describing the remaining n -producing reactions, we describe someproperties of the system of reactions above. We say that o-consumptionstalls if none of the o-consuming reactions are ever applicable again. Letzs [ (z)s; z2s) be the counts of (o); o2) consumed when o-consumptionstalls (zs is independent of the order in which the reactions happen). The n -producing reaction above ensures that the o-consuming reactions are neverstalled because y becomes too large. Also, the o-consuming reactions don’tstall if lz is a fissure line and another o) is or will eventually be available(and similarly if another o2 is or will eventually be available), because zchanges by 1 upon consumption of o) and so is still less than K.Stalling happens when and only when one of the following (exclusive)cases arise. (i) All copies of both o) and o2 have been consumed and nomore will ever be produced, so zs [ (<L(n); <B(n)). (ii) All copies of o2have been consumed and no more will ever be produced, so z2s [ <B(n)but z)s < <L(n). In this case, b−)(zs) is on a lower boundary line. To seewhy, note that if b−)(zs) were on a fissure or upper boundary line, thenthe o-consuming reaction that consumes o) would eventually be applicable,because lz is in the proper range and at least one copy of o) has yet to beconsumed. (iii) All copies of o) have been consumed and no more will everbe produced, so z)s [ <L(n), but z2s < <B(n). In this case, the line alzcontaining b−)(zs) must be an upper boundary line.20Claim 2. f(b−)(zs)) [ f(n).Proof. This is trivial in case (i) when all os have been consumed and nomore will be produced, since b−)(zs) [ n. Consider case (ii) (case (iii)is similar). Then b−)(zs) [ b−)(z)s; <B(n)), z)s < <L(n), and the linecontaining b−)(zs) is a lower boundary line. By Claim 1, n must be inDomB, because n [ b−)(<L(n); <B(n)) and <L(n) S z)s. Therefore,f(b−)(zs)) [ <B(b−)(zs)) [ <B(n) [ f(n).We now return to the last three reactions of the CRN, which are n -producing reactions; we will number them so that we can reference themlater and refer to them as deficit-clearing reactions. The next reaction clearsa positive deficit when both x and b−)(z) lie on the same fissure line:[lx; lz; y]→ [lx; lz; 0] + yn if − k < lx [ lz < kO (3.1)The last two n -producing reactions clear the deficit if b−)(z) is on a lowerboundary line and for some nonnegative integer r, b−)(z + (r; 0)) is on aline al with l [ lx mod 2K − 1. If such an r exists, let r) be the smallestsuch integer and add the following reaction:[lx; lz; y] + r)o) → [lx; lz; 0] + r)o) + yn;lz ≥ k; lz + r) [ lx mod 2K − 1; y S 0O (3.2)We add a similar reaction when the line alz containing b−)(z) is an upperboundary line, when an similarly-defined r2 exists:[lx; lz; y] + r2o2 → [lx; lz; 0] + r2o2 + yn;lz ≤ −k; lz + r2 [ lx mod 2K − 1; y S 0O (3.3)This completes the description of the CRN. We need one more claim in orderto complete the proof of the lemma:Claim 3. When o-consumption stalls, the deficit is nonnegative.3.2.1 Proof of Claim 3Proof. Let zp be the number of (o); o2) already consumed at the last timethat the deficit is cleared before o-consumption stalls, plus the number of o)or o2 that are reactants of this last deficit clearing reaction, if any (i.e., r)if the reaction is (3.2) or r2 if the reaction is (3.3)). Let np [ (n)p; n2p)be the counts of the inputs (m); m2) that have been consumed at this21time. The deficit is nonnegative when o-consumption stalls if f(b−)(zs)) ≥f(b−(zp)). We will show that f(np) ≥ f(b−)(zp)). Since f(b−)(zs)) [f(n) by Claim 2, since n ≥ np and since f is increasing on integer-valuedpoints, we then havef(b−)(zs)) [ f(n) ≥ f(np) ≥ f(b−(zp))OTo show that f(np) ≥ f(b−)(zp)), first suppose that np is on a fissureline. Note that np and b−)(zp) must be on the same fissure line, sincedeficit-clearing reactions can happen only in this case. Now suppose thatthe deficit-clearing reaction applied is (3.1), i.e., x [ np, z [ b−)(zp) andboth x and z are on the same fissure line. Sof(np) [ min(<L(np); <B(np))− ylx ≥ min{z)p; z2p} − ylx [ f(b−)(zp))ONext suppose that the deficit-clearing reaction applied is (3.2). Now, theline l containing b−)(zp) must be such that l ≥ K; otherwise the conditionthat l [ lx mod K would not hold. Then by our choice of K, which is atleast k + ymax, it must be that(<L(np); <B(np)) ≥ (z)p; z2p + ymax)OIntuitively, this is because to “get back” to np from b−)(zp) requires con-suming at least ymax more o2s. Also z)p − z2p [ l S K, so<L(np) ≥ z)p ≥ z2p +K ≥ min{z)p; z2p}+ (k + ymax);and somin{<L(np); <B(np)} ≥ min{z)p; z2p}+ ymaxOThereforef(np) [ min{<L(np); <B(np)} − yl ≥ min{z)p; z2p}+ ymax − yl≥ min{z)p; z2p} [ f(b−)(zp)OOtherwise np is not on a fissure line (although lx might be the index ofa fissure line). In this case f(np) [ min(<L(np); <B(np)). Then, regardlessof which deficit-clearing reaction is applied, we have thatf(np) [ min(<L(np); <B(np)) ≥ min{z)p; z2p} ≥ f(b−)(zp))OThus in every case we have that f(np) ≥ f(b−)(zp), and we are done.22To complete the proof of Lemma 12, we argue that once o-consumptionstalls, some deficit-clearing reaction will eventually be applicable, ensuringthat the output eventually produced is f(n). If b−)(zs) is on a fissureline then b−)(zs) must equal n, in which case n -producing reaction (3.1)is applicable. If b−)(zs) is on a boundary line then either (3.2) or (3.3)will be applicable once all inputs are consumed, since for some r, eitherb−)(zs + (r; 0)) [ n or b−)(zs + (0; r)) [ n. Thus in all cases some n -producing reaction eventually clears the deficit, ensuring that the outputproduced is f(n).3.3 Stitching LemmaLemma 13. (Stitching Lemma) Let Let f be an increasing function. Iff : N2 → N is a finite combination of output-oblivious functions whosedomains are grids, then f is output-oblivious. Also if f is the min of a finitenumber of output-oblivious functions then f is output-oblivious.Proof. Let f be a finite combination of output-oblivious functions, say f); f2; O O O ; fx,whose domains are grids. We first describe the construction for the case thatthe domain Domj of fj is a two-way-infinite grid for all j; 1 ≤ j ≤ m. Letthe offset of the jth grid be oj [ (oj;); oj;2). On input n, our CRN C firstproduces m distinct “inputs” n(j) ∈ N2 such that n ≤ n(j) and n [ n(j) ifn ∈ Domj . From these, C produces m “outputs” yj [ fj(n(j)), using CRNsCj for each fj . Finally, C produces y [ min{y); O O O ; yx}.To see that such a C is correct, i.e., that y [ f(n), note that if n ∈ Domjthen yj [ fj(n(j)) [ fj(n) [ f(n), since n [ n(j), and if n ̸∈ Domjthen yj [ fj(n(j)) ≥ f(n), since f is increasing and n(j) ≥ n. Thusf(n) [ min{y); O O O ; yx} [ y. The details of producing the n(j)s and theoutput are explained after this.When f is the min of a finite number of output-oblivious functions, sayf); f2; O O O ; fx, we can similarly stably compute each ft using an output-oblivious CRN Ct such that the species for each Ct are distinct, and thentake the min of the outputs as the result. For simplicity of notation, fix somej, let Dom′ [ Domj , let the base vectors of Dom′ be (v′); 0) and (0; v′2), andlet o′ [ (o′); o′2) be its offset. Let n(j) [ n′ [ (n′); n′2) be the smallest elementof Domj such that n ≤ n′. The following CRN X ′, which has nine reactionsin total, produces n′) copies of species m ′) and n′2 copies of species m ′2 from23a leader a′:a′ → a′(( + o)m ′) + o2m ′2a′(m + (o′) + 1)m) → a′)m + v′)m ′); for b [ 0 and b [ 1a′m( + (o′2 + 1)m2 → a′m) + v′2m ′2; for b [ 0 and b [ 1a′)m + v′)m) → a′)m + v′)m ′); for b [ 0 and b [ 1a′m) + v′2m2 → a′m) + v′2m ′2; for b [ 0 and b [ 1To produce all inputs n(1); O O O ;n(m), m copies of CRN X ′ are needed, eachwith independent copies of the species; for example, species m(j)) and m(j)2are substituted for m ′) and m ′2. Three additional reactions produce theleaders and input copies needed for each of these m independent copies ofX ′:a → a′) + O O O a′xm) → m())) + O O O m(x))m2 → m())2 + O O O m(x)2 OProducing the Output y: Let nj be the output species of the output-oblivious CRN for fj , so that its count yj [ fj(n(j)). To produce y [min{y); O O O ; yx} we need just one reaction:n) + O O O+ nx → nOThis completes the contruction for the case that all Domj are 2D grids.We now modify CRN X with additional reactions to handle the case thatsome of the Domj may be 0D grids (i.e., points) or 1D grids. The problemthat can arise is that for some j, Dom′ [ Domj may not have any pointthat is greater than input n. We add reactions that generate a species S′when this is the case. Specifically, if Dom′ contains no base vector of theform (v′); 0), we adda′)m → S′; for b [ 0 and b [ 1;and we remove reactions above that involve v′). Similarly, if Dom′ containsno base vector of the form (0; v′2), we adda′m) → S′; for b [ 0 and b [ 1Oand we remove reactions above that involve v′2. Note that S′ is produced ifand only if Dom′ has no point n′ such that n ≤ n′.As before, X contains distinct copies of these reactions for each Domjthat is not 2D, producing one or two copies of species Sj if and only if Domjhas no point n(j) such that n ≤ n(j).24Finally, we need to ensure that the ouput y produced is the min of the yjtaken over domains Domj for which n(j) ∈ Domj . To do this, we replace thesingle reaction n) + O O O+ nx → n by 2x new reactions, one for each subsetI of {1; O O O ;m}. The reaction corresponding to subset I is of the formn ′) + O O O+ n′x → n + n ′′) + O O O+ n ′′x;where n ′j [ nj if j ∈ I and n ′j [ Sj otherwise, and n ′′j is some inactivespecies if j ∈ I and n ′′j [ Sj otherwise.3.4 Final ConditionFinally we prove the sufficiency (if) direction of Theorem 1.Theorem 1 (if direction). A semilinear function f : N2 → N is output-oblivious if f is increasing and is either grid-affine or the minimum of finitelymany fissure functions.Proof. First suppose that f is grid-affine. Then by Definition 3, f is a combi-nation of affine functions f); O O O ; fx whose domains G); O O O ;Gx respectivelyare grids. By Lemma 10, ft : Gt → N is output-oblivious, 1 ≤ i ≤ m. ByLemma 13, f is output-oblivious.Otherwise f is the min of finitely many complete fissure functions f); O O O ; fx.By Definition 4, each ft is a combination of partial fissure functions on gridsof period p, for some p ∈ N. By Lemma 12, each of these partial fissurefunctions is output-oblivious. By Lemma 13, each ft is output-obliviousand also f is output-oblivious.3.5 Examples3.5.1 Example for Claim 3In Figure 3.2 a contour plot for a fissure function is provided, this fissurefunction is used in the next example which is displayed in Figure 3.3. Thefissure function in these two figures is defined as follows.25f(n) [8>>>>>>>>>>><>>>>>>>>>>>:<L(n) [ 3n) + 2n2 + 6; if n ∈ DomL i.e. n ∈ at; i ≤ −2;<L(n)− y−) [ 3n) + 2n2 + 3; if n ∈ a−);<L(n)− y( [ 3n) + 2n2; if n ∈ a(;<B(n)− y) [ 2n) + 3n2 + 1; if n ∈ a);<B(n)− y2 [ 2n) + 3n2 + 3; if n ∈ a2;<B(n)− y+ [ 2n) + 3n2 + 3; if n ∈ a+;<B(n) [ 2n) + 3n2 + 6; if n ∈ DomB i.e. n ∈ at; 4 ≤ iO(3.4)In some of the proofs and for the definition of lower and upper boundarylines, a−2 and a−+ are also considered as fissure lines with yt [ 0 instead ofbeing in DomL.As displayed in purple in Figure 3.2, if the CRN returns from an state ona line far enough from the fissure lines to a fissure line the deficit change isgoing to be non negative. This is because min{<L(n); <B(n)} − f(n) is atmost a constant and by choosing a far enough initial line min{<L(n); <B(n)}can increase arbitrary large in the return and more than this constant value,in turn this is because moving from two adjacent lines in the direction offissure lines increases the min function exactly by one. Therefore f(n) shouldnot decrease. Because of this, in the case that the deficit-clearing reactionhappens far from fissure lines, it is not going to encounter a problem. Thenext figure will argue that f is not decreasing in other complex scenarios fordeficit-clearing reactions.In Figure 3.3 an example is provided for proof of Claim 3. In this exam-ple the same fissure function as in the previous figure is used. Note that inthe first scenario of Figure 3.3 the deficit is negative atb−)(z) [ (3; 0) withf(3; 0) [ 9 because the deficit is cleared atb−)(zp) where f(b−)(zp)) [ 10.In case of a negative deficit we know that the CRN does not need to outputimmediately because we already know that f(n) is larger than the currentoutput.In Figure 3.3 in both scenarios based on lz [ 1 we know b−)(zp) lieson the line a) or one of the far lines. In scenario 1 because lx [ lz [ 1, thedeficit clearing reaction is allowed. In such a scenario if np and b−)(zp)both lie on the fissure line, because b(np) S zp (the green area) we knownp is in the intersection of the line a) and the green area. All points inthis intersection are greater than b−)(zp) (the medium darkness area) andtherefore f(np) S f(b−)(zp)) and deficit clearing reaction does not cause a26problem. Note that the case that np or b−)(zp) are not on a) is explainedin the previous paragraphs and the other figure. In the second scenario,although f(np) [ 9 < f(b−)(zp)) [ 10 and a deficit clearing reactionwould produce more outputs than the answer, because the condition lx [ lzdoes not hold the deficit clearing reaction is not allowed.3.5.2 Example for Lemma 9Figure 3.4 shows an example for the Lemma 9. Here the conversion ofdomains is only shown for a linear set.27Figure 3.2: A contour plot for the fissure function used in the next exampleand defined in Equation 3.4. The red arrow shows a transition with negativedeficit change. The function can not take back its output so it should notcause negative deficits which last until after when the execution is finished.The purple arrow displays a return to the fissure lines from a far line. If theinitial line is far enough from the fissure lines, the change in the deficit isgoing to be positive or non-negative similar to the purple arrow.28Figure 3.3: Similar to the proof of Claim 3, assume that zp is the number of(o); o2) already consumed and np is the number of (m); m2). Two scenarioswith the same path for (o); o2) consumption (purple) but different pathsfor (m); m2) consumption (red) are provided.29Figure 3.4: Based on Lemma 9, each semilinear domain can be expressedas the union of sets like Gt ∩ Tt, where Gt is a grid with a period p andTt is an intersection of threshold sets and where all grids share the sameperiod. In this example all Tt are the same but they can be different in thegeneral case. The left figure shows a linear set with the base {x); x2} wherex) [ (2; 2) and x2 [ (1; 4). The right figure shows the same set expressedas union of Gt ∩ T . Each grid in the right figure has a period of 6 and thereare a total of 6 grids and T is the intersection of two threshold sets definedby x · (−2; 2) ≥ 0 and x · (4;−1) ≥ 0.30Chapter 4Time Analysis4.1 The Kinetic Model and BasicsThe stochastic model of chemical kinetics describes interactions involvingsmall number of molecules [14, 20]. This subsection is structured similar toDavid Doty’s lecture notes [12]. In this analysis we assume that the prob-ability of a reaction taking place follows an exponential distribution withexpected value of ) .The rate  depends on volume v and the number of available reactantspecies.Here the following formula is used for the rate  of a given reaction withreactants S); OOO; Sd. This formula is with respect to a given configuration,in which the count of species St is #St. [ kO1v‖r‖−)d∏t=)#St!(#St − r(St))! ;where ||r|| is the count of the molecules consumed in the reaction and r(St)is the count of the molecules of the ith species consumed in the reaction andk is a constant independent of species count. We will assume that k [ 1 tosimplify the expressions.Here the time complexity refers to the expected amount of time needed forthe CRN to stabilize. In the examples this amount of time is shown by iand the expected amount is shown by Z[i ].For example the rate for the reaction : V→ B with #V [ n is  [ n andthe time complexity is ) [ )n . This rate for the reaction : V+ V → B is [ n(n−))v .A series of scenarios are analyzed by other authors. The following settingsand their time complexities are included here.1. #V [ n initially in volume n: : V→ B31The time for each reaction is independent of the previous ones. So,Z[i ] [∑Z[it] [∑ 1i[ (lnn);where it is the amount of time needed for the reaction when #V [ i.2. #V [ #B [ 1 initially in volume n: : V+B → XOOnly one reaction occurs with  [ )∗)n . So,Z[i ] [ nO3. #V [ #B [ n initially in volume n: : V+B → XOThe last reaction needs (n) time, the rest of reactions are also within(n). That is the final expected time is also (n) as follows,Z[i ] [∑Z[it] [∑ ni ∗ i [ (n);where it is defined similar to scenario 1.4. Minimum. in case of minimum with two species and #V [ #B this isthe same as the pairing off reactions in scenario 3 and has an expectedtime of (n). When #V S #B the time of individual reactions withthe same amount of #B decreases and therefore the time is d(n).When the difference of #V and #B is large the time can be below n.For example when #V ≥ 2×#B,Z[i ] [∑Z[it] ≤∑ n(#V−#B)i ≤nn+∑ 1i[ d(lg n)OOther cases similarly can be analyzed. Later we will show similar results forcase-specific scenarios.324.2 Output Oblivious CRN Time Analysis4.2.1 Basics with LeaderReaction with LeaderAssume #V [ n and #a [ 1 initially in volume n. : V+ a→ B + aOSimilar to the leaderless scenario, if it is the time needed for the reactionwhen count of V is i, then it are independent.Z[i ] [∑Z[it] [∑ ni ∗ 1 [ (n lg n)OMinimum with Multiple SpeciesAssume #V) [ v),#V2 [ v2,...,#Vv [ vv and #a [ 1 initially in volumen. Here we assume that no other reactions have the Vt as reactants. Wecan rewrite the following reaction, : V) +V2 + OOO+Vv + a→ B + a;as the set of reactions,a→ a(((::()a(m1::mi=(::mk) +Vt → a(m1::mi=)::mk)a())::)) → B + a(((::()OThis way we only use reactions that have two reactants and are faster.In case that there are other reactions that want to use the species temporar-ily absorbed by the leader, it is still possible to construct a CRN with 2reactants. In this case the other reactions also should be able to use the ab-sorbed species. For example in the subsection allocated to fissure functiontime analysis two reactions use the same species and both are replaced byreactions with input size of 2.The time itj that one instance of the ith species with count j is consumed bythe leader when it is consumable by the leader and the time i ′t that leaderoutputs the ith instance of B when possible are all independent from eachother. Although more than one reaction might be possible at a time, andthis gives a final time which is less than the sum of the reaction times, we33know that at least one reaction is possible at a time so the sum of individualreaction times give an upper bound for the total time needed by CRN.Z[i ] ≤∑t;jZ[itj ] +∑tZ[i ′t ] [ (∑t;jnj) + min(v); OO; vv)≤ (∑tn log(min(v); OO; vv))) + min(v); OO; vv) [ d(n lg n)OThe bound is tight when min(v); OO; vv) is ((n).Although it is possible to construct CRNs that do not have the requirementthat no other reactions should use the reactants of the replaced reaction, thestitching lemma’s minimum operations meets this requirement and thereforeno other reaction than the minimum reaction needs to be changed.Comparing to the original minimum reaction with k species (reaction ),in case when #V) [ #V2 [ OOO [ #Vv [ n the reaction should happenn times and the reaction with #V) [ i has a time of nktk , so consideringonly the last reaction the total time is ((nv) (or nv−) if the reaction wasleaderless). In a similar way to the pairing off reaction that is the scenario 3of the previous section, it can be shown that the rest of time is d(nv) andthe total time is (nv) because ∑ )tkis constant.4.2.2 Output Oblivious CRNAffine FunctionSimilar to the minimum with multiple species, this function’s reactions canbe rewritten to only take one instance of a single species at a time.There were three reactions in the CRN of an affine function. Each reactionwas in the form of,a+ vm) + bm2 → a′ + xnOThe corresponding two reactant reactions can be written as follows,a→ a((;()a(t;j) +m) → a(t+);j) for i < va(t;j) +m2 → a(t;j+)) for j < ba(l;m) → a′ + xnBecause more than one reaction is possible at a time, the other reactionsshould be able to consume absorbed reactants.34Fissure FunctionAssume that all o-producing reactions happen before all o-consuming andn -producing reactions. This gives an upper bound for time. This is becausealthough o-producing reactions change the leader-state, o-consuming reac-tions do not depend on the leader state lx. When all m are consumed thelargest possible upper bound for amount of time for o consumption is whenno o is consumed. We will see this upper bound later.For the o-producing reactions, they are analyzed in the reactions with leadersubsection and they are (n lg n). Because there are two of these reactionswe know that the maximum of the time needed is less than the sum of bothtimes which again has an expectation of (n lg n).For the o-consuming reactions, this is similar to the two previous subsec-tions, but as another example I will write this in more detail.Assume that there are zt copies of ot when mt are completely consumed.Let itj be the time spent by the CRN to consume an instance of ot whenthere is j instance remaining and the reaction is possible. The quantitiesitj are independent of each other. The total time can be less than the sumof all itj when more than one reaction is possible at a time, because alwaysat least one of the o-consuming reactions are possible the sum gives a validupper bound.Z[iZ-consuming] ≤∑t;jZ[itj ] [ (∑t;jnj) ≈ (∑tn log(zt)) [ d(n lg n)OThe upper bound is maximum when all o-producing reactions happen beforeall o-consuming reactions as stated before.For the final n -producing reaction, it may be a d(1) n -producing reaction ormay consume more than one reactant other than the leader. In the secondcase (that is Equation 3.2 and Equation 3.3) because different reactionsconsume the same reactants with different amount, the trick in the minimumwith multiple species subsection should be modified. Instead of the followingreactions,a+ i×V→ a′ + i×V+Ba+ j ×V→ a′ + j ×V+B′;where i×V means i instance of V and j < i. We can write,a→ a(av +V→ av+) for k ≤ i35av → a′v +B for k ≥ iav → a′v +B′ for k ≥ j;and for all other reactions involving a, similar reactions with av should beadded which releases k instances of V. Applying this for n -producing reac-tions will not affect the execution. The time analysis when all o-consumingreactions are finished is as follows, the time to consume r) instance of o) orr2 instance of o2 is d(n lg n) and final n -producing reaction is d(1). All setof reactions are either d(n lg n) or (n lg n), so the total time of the CRNis (n lg n).Stitching LemmaAs discussed before for the minimum operation in the stitching lemma thed(n lg n) minimum operation constructed in the previous sections can beused. For the rest of reactions we can assume that all the other reactionsshould happen before any minimum reaction. This gives an upper bound ofd(n lg n) for the time.All other reactions are analyzed in the reactions with leader subsection.Although a few of the reactions take more than one reactant except theleader similar to the minimum with multiple species subsection the reactionscan be rewritten to take only one reactant other than the leader at a time.This is because different reactions don’t use the same reactants at the sametime. The preparation reactions are d(n lg n) and the minimum operationis d(n lg n), so if the individual functions are d(n lg n) the stitched CRNis d(n lg n). This bound is tight because many of reactions with leadercan take ((n log n) time alone. (For example the preparation reactions arereactions with leaders which were analyzed before, and are (n lg n)).Final Time ComplexityAll the fissure functions and affine functions can be constructed to work ind(n lg n). These functions can be stitched in an operation that keeps thetime complexity below d(n lg n). This bound is tight as mentioned in theprevious section.All this analysis is correct as long as the volume is d(n). It is easy to verifythat a volume of d(n) is enough for the computation. Both of the CRNs forthe construction of fissure functions and the stitching lemma are functionalwith a volume of d(n) for an input of size d(n).36Bibliography[1] Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exactmajority in population protocols. In Proceedings of the 2015 ACMSymposium on Principles of Distributed Computing, pages 47–56. ACM,2015.[2] Dana Angluin, James Aspnes, and David Eisenstat. Fast computationby population protocols with a leader. In Dolev S. (eds) DistributedComputing (DISC), Lecture Notes in Computer Science, volume 4167,pages 61–75. Springer, Berlin, Heidelberg, 2006.[3] Dana Angluin, James Aspnes, and David Eisenstat. Stably computablepredicates 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.[4] Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. Thecomputational power of population protocols. Distributed Computing,20(4):279–304, 2007.[5] Adam Arkin, John Ross, and Harley H McAdams. Stochastic kineticanalysis of developmental pathway bifurcation in phage -infected es-cherichia coli cells. Genetics, 149(4):1633–1648, 1998.[6] Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computesapproximate majority. Scientific Reports, 2:656, 2012.[7] Cameron Chalk, Niels Kornerup, Wyatt Reeves, and David Soloveichik.Composable rate-independent computation in continuous chemical re-action networks. In Milan Ceska and David Safránek, editors, Com-putational Methods in Systems Biology, pages 256–273, Cham, 2018.Springer International Publishing.[8] Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic func-tion computation with chemical reaction networks. Natural Computing,13(4):517–534, Dec 2014.37[9] Ben Chugg, Hooman Hashemi, and Anne Condon. Output-obliviousstochastic chemical reaction networks. In Conference on Principles ofDistributed Systems, 2018.[10] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, andEric Ruppert. Secretive birds: Privacy in population protocols. InE. Tovar, P. Tsigas, and H. Fouchal, editors, International ConferenceOn Principles Of Distributed Systems, pages 329–342, 2007. LectureNotes in Computer Science, vol 4878. Springer.[11] Leonard Eugene Dickson. Finiteness of the odd perfect and primitiveabundant numbers with n distinct prime factors. American Journal ofMathematics, 35(4):413–422, 1913.[12] David Doty. David doty’s ecs 289 lecture notes. pages 25–27. https://web.cs.ucdavis.edu/~doty/winter2016ecs289/notes.pdf.[13] David Doty and Monir Hajiaghayi. Leaderless deterministic chemicalreaction networks. Natural Computing, 14(2):213–223, 2015.[14] Daniel T. Gillespie. Exact stochastic simulation of coupled chemicalreactions. In Journal of Physical Chemistry, 1977.[15] Allen Hjelmfelt, Edward D Weinberger, and John Ross. Chemical im-plementation of neural networks and Turing machines. Proceedings ofthe National Academy of Sciences, 88(24):10983–10987, 1991.[16] Hua Jiang, Marc D Riedel, and Keshab K Parhi. Digital signal pro-cessing with molecular reactions. IEEE Design and Test of Computers,29(3):21–31, 2012.[17] Nils E Napp and Ryan P Adams. Message passing inference with chem-ical reaction networks. In Advances in Neural Information ProcessingSystems, pages 2247–2255, 2013.[18] Lulu Qian and Erik Winfree. Scaling up digital circuit computationwith DNA strand displacement cascades. Science, 332(6034):1196–1201,2011.[19] Eric E. Severson, David Haley, and David Doty. Com-posable computation in discrete chemical reaction networks.https://arxiv.org/pdf/1903.02637.pdf, 2019.38[20] David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck.Computation with finite stochastic chemical reaction networks. NaturalComputing, 7, 2008.[21] David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universalsubstrate for chemical kinetics. Proceedings of the National Academyof Sciences, 107(12):5393–5398, 2010.[22] Chris Thachuk and Anne Condon. Space and energy efficient compu-tation with DNA strand displacement systems. In D. Stefanovic andA. Turberfield, editors, International Workshop on DNA-Based Com-puters, pages 135–149, 2012. Lecture Notes in Computer Science, vol7433. Springer.[23] David Yu Zhang, Rizal F Hariadi, Harry MT Choi, and Erik Win-free. Integrating DNA strand-displacement circuitry with DNA tileself-assembly. Nature Communications, 4:1965, 2013.39Appendix: Proofs of LemmasA.1 Proof of Lemma 11Proof. Let <(n) [ 〈a; n〉+v( and G [ {(x) ); x2 2)+o : t ∈ N}. Let n′ ∈G \ T . Assuming that n′ ≥ m, we can find some n ∈ Y with n ≤ n′ whichshares either the n) or n2 projection of n′. Assume that it is the former;the other case is similar. We can write n′ [ (x); 0) ) + (0; x2)( 2 + ) + oand n [ (x); 0) ) + (0; x2) 2 + y for some ); 2; ∈ N. Notice that<(n′) [ <(n) + 〈a; (0; x2)〉 and since <(n) ∈ N it remains only to showthat 〈a; (0; x2)〉 ∈ N. Since Y is a wedge domain, the threshold sets whichdefine its upper and lower boundary are not parallel, meaning that we canfind two points in Y, n) and n2 such that n) − n2 [ (0; x2) (indeed thereare infinitely many such points). Thus, 〈a; (0; x2)〉 [ <(n)) − <(n2) ∈ N,completing the proof.40
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Sufficiency condition for output-oblivious chemical reaction networks and run-time analysis
Text