Execution bounded chemical reaction networks

Abstract: Chemical reaction networks (CRNs) model systems where molecules or agents interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. Although traditionally used to model natural chemical systems, CRNs are also studied as a programming language for describing the desired behavior of synthetic chemical systems. Synthetic CRNs can compute Boolean-valued predicates $\phi \colon \mathbb{N}^d \to \{0,1\}$ and integer-valued functions $f\colon \mathbb{N}^d \to \mathbb{N}$; for instance X1 + X2 → Y can be thought to compute the function min(x1,x2).

We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). Our main negative results, showing limitations on the computational power of execution bounded CRNs, are based on characterizing execution bounded CRNs as precisely those that have a "linear potential function": a nonnegative linear function of the network's state, which every reaction strictly decreases. This equivalence is proved using a variant of Farkas' Lemma and may be of independent interest.

(joint work with Ben Heckmann)

algebraic geometrydynamical systemsprobability

Audience: researchers in the topic

( slides | video )

---

Seminar on the Mathematics of Reaction Networks

Series comments: Subscription link: list.ku.dk/postorius/lists/morn.list.ku.dk/

This seminar series focuses on progress in mathematical theory for the study of reaction networks, mainly in biology and chemistry. The scope is broad and accommodates works arising from dynamical systems, stochastics, algebra, topology and beyond.

We aim at providing a common forum for sharing knowledge and encouraging discussion across subfields. In particular we aim at facilitating interactions between junior and established researchers. These considerations will be represented in the choice of invited speakers and we will strive to create an excellent, exciting and diverse schedule.

The seminar runs twice a month, typically on the 2nd and 4th Thursday of the month, at 17:00 Brussels time (observe that this webpage shows the schedule in your current time zone). Each session consists of two 25-minute talks followed by 5-minute questions. After the two talks, longer discussions will take place for those interested. To this end, we will use breakout rooms. For this to work well, you need to have the latest version of Zoom installed (version 5.3.0 or higher), and use the desktop client or mobile app (not supported on ChromeOS).

We look forward hearing about new work and meeting many of you over zoom! Many of the talks are recorded; to see the recording, from Past Talks, open details of the listed talk for a video link.

The organizers.

---