Technical Reports

Self-assembly is the programmatic design of particle systems that coalesce into complex superstructures according to simple, local rules. Such systems of square tiles attaching edgewise are capable of Turing-universal computation and ecient construction of arbitrary shapes. In this work we study the staged tile assembly model in which sequences of reactions are used to encode complex shapes using fewer tile species than otherwise possible. Our main contribution is the analysis of these systems by comparison with context-free grammars (CFGs), a standard model in formal language theory. Considering goal shapes as strings (one dimension) and labeled polyominoes (two dimensions), we perform a ne-grained comparison between the smallest CFGs and staged assembly systems (SASs) with the same language. In one dimension, we show that SASs and CFGs are equivalent for a small number of tile types, and that SASs can be signicantly smaller when more tile types are permitted. In two dimensions, we give a new denition of generalized context-free grammars we call polyomino context-free grammars (PCFGs) that simultaneously retains multiple aspects of CFGs not found in existing denitions. We then show a one-sided equivalence: for every PCFG deriving some labeled polyomino, there is a SAS of similar size that assembles an equivalent assembly. In the other direction, we give increasingly restrictive classes of shapes for which the smallest SAS assembling the shape is exponentially smaller than any PCFG deriving the shape.