Degree Type

Dissertation

Date of Award

2016

Degree Name

Doctor of Philosophy

Department

Computer Science

Major

Computer Science

First Advisor

James I. Lathrop

Second Advisor

Jack H. Lutz

Abstract

In this thesis, we present four results concerning the computing capabilities of chemical reaction networks (CRNs) under deterministic mass action semantics: (1) we introduce a modular method for computing concentration signals using CRN extension operators; (2) we present a thorough analysis of two CRN signal restoration algorithms that prevent certain concentration signals from degrading over time; (3) we introduce a new model called input/output chemical reaction networks (I/O CRNs) which generalizes the CRN model to allow receiving input signals over time; and (4) we investigate what I/O CRNs can compute robustly and prove that I/O CRNs are capable of robustly simulating any nondeterministic finite automaton (NFA).

CRN extension operators are operations that can be applied to a CRN to add extra functionality without affecting its original behavior. We show that common operators such as addition, multiplication, integration, and many others can be characterized as CRN extension operators. By iteratively applying these extensions, complex concentration signals can be modularly constructed from simple CRNs. To explore the full generality of these extensions, we introduce a notion of weakly CRN-computable signals and show that any CRN that can weakly compute a signal can be extended to exactly compute it.

The two signal restoration algorithms that we investigate are related to the approximate majority algorithm for population protocols originally developed by Angluin, Aspnes, and Eisenstat. Under deterministic semantics, these algorithms are commonly used to prevent discrete memory from deteriorating over time. We investigate the behavior of these algorithms in the presence of adversarial reactions and show that under modest conditions they are capable of maintaining discrete memory indefinitely. We also give tight analytical bounds on how these algorithms evolve over time.

The I/O CRN model that we introduce has two important impacts. (1) Concentration signals are a more natural way to provide arbitrarily long inputs to a CRN. Classical CRNs are restricted to encoding inputs into the initial state of the system which makes providing an arbitrarily long input (e.g. a binary string) quite difficult. (2) It promotes modular design of CRNs. Designing chemical systems from modular components that communicate via concentration signals is now possible, and we demonstrate its effectiveness in multiple constructions including our I/O CRN implementation of NFAs.

Our notion of robustness requires that an I/O CRN tolerate perturbations with respect to four things, namely, its initial state, rate constants, input signal, and the measurement of its output signal. We investigate what I/O CRNs are capable of computing under this notion of robustness, and we prove that I/O CRNs can robustly compute the regular languages by simulating an NFA in real time.

Copyright Owner

Titus Klinge

Language

en

File Format

application/pdf

File Size

116 pages

Share

COinS