Staged self-assembly and polyomino context-free grammars.
详细信息
文摘
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 efficient 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 fine-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 significantly smaller when more tile types are permitted. In two dimensions,we give a new definition of generalized context-free grammars we call polyomino context-free grammars PCFGs)} that simultaneously retains multiple aspects of CFGs not found in existing definitions. 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.