Editing CRNs with limited geometry (section)

= Workshop progress =

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

=== Extended CRN syntax ===

==== Prior work ====
* DSD <ref name="dsd">Lakin, M. R., Youssef, S., Cardelli, L., & Phillips, A. (2012). Abstractions for DNA circuit design. Journal of The Royal Society Interface, 9(68), 470-486.</ref>

** DSD already handles some polymer classes, focused on DNA strand displacement

* BGF: Biochemical ground form <ref name="bgf">Cardelli, L., & Zavattaro, G. (2008). On the computational power of biochemistry. In Algebraic Biology (pp. 65-80). Springer Berlin Heidelberg.</ref>
* Kappa <ref name="kappa">Danos, V., Feret, J., Fontana, W., Harmer, R., & Krivine, J. (2008). Rule-based modelling, symmetries, refinements. In Formal Methods in Systems Biology (pp. 103-122). Springer Berlin Heidelberg.</ref>

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

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

=== 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 semi-linear 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<ref name="dsd">Caleb Malchik, Andrew Winslow. (2014). Tight Bounds for Active Self-Assembly Using an Insertion Primitive. [arxiv | http://arxiv.org/abs/1401.0359] </ref> 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.

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

=== Tree self-assembly ===

'''Question''': Self-assemble a single tree from uniform components. Then light-up the left spine. How cheaply/fast can we do it? 

* Here is an algorithm and simulation: [[:File:Tree assembly in pi-calculus.pdf]]