Back to search

University of British Columbia

Sufficiency condition for output-oblivious chemical reaction networks and run-time analysis

Abstract

dc: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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hashemi, Hooman

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/72223

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hashemi, Hooman. Sufficiency condition for output-oblivious chemical reaction networks and run-time analysis. master's thesis, University of British Columbia, 2019. http://hdl.handle.net/2429/72223