Authors: David Doty
Publish Date: 2015/08/20
Volume: 15, Issue: 1, Pages: 41-49
Abstract
Three results are shown on producibility in the hierarchical model of tile selfassembly It is shown that a simple greedy polynomialtime strategy decides whether an assembly α is producible The algorithm can be optimized to use Oalpha log 2 alpha time Cannon et al STACS 2013 proceedings of the thirtieth international symposium on theoretical aspects of computer science pp 172–184 2013 showed that the problem of deciding if an assembly α is the unique producible terminal assembly of a tile system mathcal T can be solved in Oalpha 2 mathcal T + alpha mathcal T2 time for the special case of noncooperative “temperature 1” systems It is shown that this can be improved to Oalpha mathcal T log mathcal T time Finally it is shown that if two assemblies are producible and if they can be overlapped consistently—ie if the positions that they share have the same tile type in each assembly—then their union is also producible The author is very grateful to HoLin Chen David Soloveichik Damien Woods Matt Patitz Scott Summers Robbie Schweller Ján Maňuch Ladislav Stacho Andrew Winslow for many insightful discussions and to anonymous reviewers for their detailed and useful comments The author was supported by NSF Grants CCF1219274 and CCF1162589 and the Molecular Programming Project under NSF Grants 0832824 and 1317694 and by a Computing Innovation Fellowship under NSF Grant 1019343
Keywords: