Sufficiency condition for output-oblivious chemical reaction networks and run-time analysis
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Hashemi, Hooman
issued: 2019-11-07T18:32:40Z
issued: 2019
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: 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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/72223
note: 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 comp…
has type: Thesis/Dissertation
date issued: 2020-05
is shown at: 10.14288/1.0385125
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/72223