The power of duples (in self-assembly): It's not so hip to be square

• Published in: Theoretical computer science 2018-09, Vol.743, p.148-166
• Main Authors: Hendricks, Jacob, Patitz, Matthew J., Rogers, Trent A., Summers, Scott M.
• Format: Article
• Language: English
• Subjects: Algorithmic self-assembly; Computation; Self-assembly; Simulation; Temperature 1
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2015.12.008

In this paper we define the Dupled abstract Tile Assembly Model (DaTAM), which is a slight extension to the abstract Tile Assembly Model (aTAM) that allows for not only the standard square tiles, but also “duple” tiles which are rectangles pre-formed by the joining of two square tiles. We show that the addition of duples allows for powerful behaviors of self-assembling systems at temperature 1, meaning systems which exclude the requirement of cooperative binding by tiles (i.e., the requirement that a tile must be able to bind to at least 2 tiles in an existing assembly if it is to attach). Cooperative binding is conjectured to be required in the standard aTAM for Turing universal computation and the efficient self-assembly of shapes, but we show that in the DaTAM these behaviors can in fact be exhibited at temperature 1. We then give a lower bound on the tile complexity for building thin rectangles in the DaTAM that matches the analogous lower bound in the aTAM. Finally, we present a series of results which prove that the temperature-2 aTAM and temperature-1 DaTAM have mutually exclusive powers. That is, each is able to self-assemble shapes that the other can't, and each has systems which cannot be simulated by the other. Beyond being of purely theoretical interest, these results have practical motivation as duples have already proven to be useful in laboratory implementations of DNA-based tiles.