PhD Defense: Staged Self-Assembly and Polyomino Context-Free Grammars

Abstract

Self-assembly is the programmatic design of particle systems that coalesce into complex superstructures according to simple, local rules. Self-assembling 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, and polyomino context-free grammars (PCFGs), a new generalization of context-free grammars to two dimensions. We show that any CFG or PCFG deriving a shape can be converted into a SAS of nearly the same size that assembles an equivalent shape. In the other direction, we show that for some strings and polyominoes, SASs assembling them are far smaller than CFGs deriving them. Along the way we examine related problems on CFGs, PCFGs, and polyominoes, and highlight some novel aspects of self-assembling systems.