BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:David Doty (University of California\, Davis)
DTSTART:20240509T150000Z
DTEND:20240509T153000Z
DTSTAMP:20260421T124005Z
UID:MoRN/92
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/MoRN/92/">Ex
 ecution bounded chemical reaction networks</a>\nby David Doty (University 
 of California\, Davis) as part of Seminar on the Mathematics of Reaction N
 etworks\n\n\nAbstract\nChemical reaction networks (CRNs) model systems whe
 re molecules or agents interact according to a finite set of reactions suc
 h as A + B → C\, representing that if a molecule of A and B collide\, th
 ey 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 system
 s. Synthetic CRNs can compute Boolean-valued predicates $\\phi \\colon \\m
 athbb{N}^d \\to \\{0\,1\\}$ and integer-valued functions $f\\colon \\mathb
 b{N}^d \\to \\mathbb{N}$\; for instance X1 + X2 → Y can be thought to co
 mpute the function min(x1\,x2).\n\nWe study the computational power of exe
 cution bounded CRNs\, in which only a finite number of reactions can occur
  from the initial configuration (e.g.\, ruling out reversible reactions su
 ch as A ⇌ B). Our main negative results\, showing limitations on the com
 putational power of execution bounded CRNs\, are based on characterizing e
 xecution bounded CRNs as precisely those that have a "linear potential fun
 ction": a nonnegative linear function of the network's state\, which every
  reaction strictly decreases. This equivalence is proved using a variant o
 f Farkas' Lemma and may be of independent interest.\n\n(joint work with Be
 n Heckmann)\n
LOCATION:https://researchseminars.org/talk/MoRN/92/
END:VEVENT
END:VCALENDAR