CRNs with limited geometry
Contents 
[edit] Problem context before workshop
Chemical reaction networks are known to be Turinguniversal with probability $1\epsilon$ (for any $\epsilon>0$) [^{[1]}.] CRNs augmented with a constant number of stacks are Turinguniversal ^{[2]}. This was demonstrated using a DNA strand displacement system construction that exploited the fact that DNA can easily form polymers. The stacks in that construction behave as one would expect: a molecule can be added to the top of the stack, can be removed from the top of the stack, and molecules not on the top are not accessible to other reactions. A stack of type $i$ initiates from a special subunit molecule called $\bot_i$. Simplifying details from ^{[2]}, this leads to CRN reactions of the form:
$$ \begin{align} [\bot_i \ldots X] + Y &\rightarrow [\bot_i \ldots XY]\\ [\bot_i \ldots XY] + POP_i &\rightarrow [\bot_i \ldots X] + Y \end{align} $$
[edit] Initial context assumption
As with many results that demonstrate CRNs capable of complex computation ^{[1]}^{[3]}, the stack machine construction in ^{[2]} assumes that certain molecular species are present in exact initial quantities, in particular there is exactly one copy of each stack.
[edit] Problem overview & questions
What is the power of CRNs augmented with stacks, without the initial context assumption? (i.e., the concentrations of stack subunit species, $\bot_i$, are given as part of the input.) The inspiration of this question can be found in the ability for DNA strand displacement systems to form polymers (complexes consisting of multiple DNA strands bound via hybridization of complementary domains). While polymers can simulate stacks, they are more general and open up new possibilities for programming CRNs.
Interesting thought experiments in this model may include:
 Beginning from a population of input $X$, can stacks be used to output $\log(X)$ copies of an output species $Y$?
 Could consensus of two input species $X$ and $Y$ be computed exactly, and efficiently, with the use of a constant number of stack types?
 What additional computational power, if any, arises when the model is broadened to included:
 double ended stacks / queues
 stacks/queues/polymers that can be efficiently concatenated with another, at their ends
 polymers that can be efficiently "merged" with another, at multiple locations along the polymer
[edit] CRNs with complexation/decomplexation
In a 2010 paper "Turing universality of the Biochemical Ground Form" Cardelli and Zavattaro define an extension of (an equivalent language to) CRNs with operations of complexation and decomplexation, and show that the extended language (BGF) is Turing universal by emulating a register machine (where registers are stacks). But in BGF stacks are not builtin, and BGF can represent pretty much any complex dynamic polymer with a finite program.
Questions:
 Can this be useful as a formal language (analogously to CRN) to investigate expressibility questions involving polymerization?
 Is there a general DSD implementation of BGF (using DNA's ability to form complexes), the same way there is a DSD implementation of CRN?
[edit] Workshop progress
[edit] High level goals
 Strand displacement systems can naturally form polymers
 Extend syntax of CRNs to consider polymer molecules
 What can they compute?
 What shapes/patterns (algorithmic) can they form?
[edit] Extended CRN syntax
[edit] Prior work
 DSD ^{[4]}

 DSD already handles some polymer classes, focused on DNA strand displacement
 BGF: Biochemical ground form ^{[5]}
 Kappa ^{[6]}
[edit] Future work
Desired: syntax for arbitrary polymers; higher level description of different polymer classes
.... motivation from CRNs
Question: what is a an arbitrary polymer structure?
[edit] Classes of polymers
 Linear
 Stacks, queues (and double ended variants)
 Tapes (i.e. like a TM, random access to any monomer in the polymer)
 Circular tapes (anything more than tape? clockwise TM?)
 Tree shapes
 Arbitrary graphs
[edit] Computational power of polymer classes
Question: what computational power does each class of polymers exhibit, when described as augmented CRNs?
Motivating example: CRNs in a well mixed solution cannot stably compute beyond semilinear functions. Can augmented CRNs?
Ex: Tree polymer construction from Luca. (CHECK. Construct tree of height $\Theta(\log n)$ in expected time $O(\log n)$. One spline of tree forms active molecules. This would effectively compute f(x)=\Theta(\log x ) if correct. Well mixed CRNs cannot.)
Prior work Chen and Dabby, and Malchik and Winslow^{[4]} work on a polymer model. The latter paper shows that with $k$ DNA hairpin monomer types, we can deterministically construct polymers of length $ 2^{\Theta{(k^{3/2})} } $, quickly; and that the expressive power of these systems is exactly the context free languages.
[edit] Constructing shapes / patterns with polymer classes
Question: Which structures can you build?
 On a tape, for example, can you build context free grammars, regular expressions,... ?
 Do other classes give more 'context' / power?
[edit] Tree selfassembly
Question: Selfassemble a single tree from uniform components. Then lightup the left spine. How cheaply/fast can we do it?
 Here is an algorithm and simulation: File:Tree assembly in picalculus.pdf
[edit] References
 ↑ ^{1.0} ^{1.1} Soloveichik, D., Cook, M., Winfree, E., & Bruck, J. (2008). Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4), 615633.
 ↑ ^{2.0} ^{2.1} ^{2.2} Qian, L., Soloveichik, D., & Winfree, E. (2011). Efficient Turinguniversal computation with DNA polymers. In DNA computing and molecular programming (pp. 123140). Springer Berlin Heidelberg.
 ↑ Thachuk, C., & Condon, A. (2012). Space and energy efficient computation with DNA strand displacement systems. In DNA Computing and Molecular Programming (pp. 135149). Springer Berlin Heidelberg.
 ↑ ^{4.0} ^{4.1} Lakin, M. R., Youssef, S., Cardelli, L., & Phillips, A. (2012). Abstractions for DNA circuit design. Journal of The Royal Society Interface, 9(68), 470486.
 ↑ Cardelli, L., & Zavattaro, G. (2008). On the computational power of biochemistry. In Algebraic Biology (pp. 6580). Springer Berlin Heidelberg.
 ↑ Danos, V., Feret, J., Fontana, W., Harmer, R., & Krivine, J. (2008). Rulebased modelling, symmetries, refinements. In Formal Methods in Systems Biology (pp. 103122). Springer Berlin Heidelberg.