Editing CRNs with limited geometry (section)

= Problem context before workshop =

Chemical reaction networks are known to be Turing-universal with probability $1-\epsilon$ (for any $\epsilon>0$) [<ref name="SCWB2008">Soloveichik, D., Cook, M., Winfree, E., & Bruck, J. (2008). Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4), 615-633.</ref>.] CRNs augmented with a constant number of ''stacks'' are Turing-universal <ref name="QSW2011">Qian, L., Soloveichik, D., & Winfree, E. (2011).  Efficient Turing-universal computation with DNA polymers. In DNA computing and molecular programming (pp. 123-140). Springer Berlin Heidelberg.</ref>.   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 <ref name="QSW2011" />, 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}
$$

==== Initial context assumption ====

As with many results that demonstrate CRNs capable of complex computation <ref name="SCWB2008" /><ref name="TC2012">Thachuk, C., & Condon, A. (2012). Space and energy efficient computation with DNA strand displacement systems. In DNA Computing and Molecular Programming (pp. 135-149). Springer Berlin Heidelberg.</ref>, the stack machine construction in <ref name="QSW2011" /> assumes that certain molecular species are present in exact initial quantities, in particular there is exactly one copy of each stack.

=== 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

=== 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 built-in, 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?