∂IFFERENCE
Complexity theory with discrete ODEs
Théorie de la complexité avec des équations différentielles discrètes
Program
(Physical meeting. Talks & discussions)
Place: Université de Paris (Building: Sophie Germain)
- Compiling Elementary Mathematical Functions into Finite Chemical Reaction Networks via a Polynomialization Algorithm for ODEs: Mathieu Hemery
Abstract: The Turing completeness result for continuous chemical reaction networks (CRN) shows that any computable function over the real numbers can be computed by a CRN over a finite set of formal molecular species using at most bimolecular reactions with mass action law kinetics. The proof uses a previous result of Turing completeness for functions defined by polynomial ordinary differential equations (PODE), the dual-rail encoding of real variables by the difference of concentration between two molecular species, and a back-end quadratization transformation to restrict to elementary reactions with at most two reactants.
In this talk, I will present a polynomialization algorithm of quadratic time complexity to transform a system of elementary differential equations in PODE. This algorithm is used as a front-end transformation to compile any elementary mathematical function, either of time or of some input species, into a finite CRN.
I will also present the performance of our compiler on a benchmark of elementary functions relevant to CRN design problems in synthetic biology specified by mathematical functions. In particular, the abstract CRN obtained by compilation of the Hill function of order 5 is compared to the natural CRN structure of MAPK signalling networks.
- Discrete ODEs & Non-determinism: Anatole Dahan.