On the effects of hierarchical self-assembly for reducing program-size complexity

• Published in: Theoretical computer science 2021-11, Vol.894, p.50-78
• Main Authors: Cannon, Sarah, Demaine, Erik D., Demaine, Martin L., Eisenstat, Sarah, Furcy, David, Patitz, Matthew J., Schweller, Robert, Summers, Scott M., Winslow, Andrew
• Format: Article
• Language: English
• Subjects: Abstract tile assembly model; Algorithmic self-assembly; Hierarchical self-assembly
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2021.09.011

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the “seedless” 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or “programs”, in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model.