Speed of Assembly in the 2HAM

From self-assembly wiki
(Redirected from Speed of Assembly)
Jump to navigation Jump to search

Since the 2HAM allows for assemblies to begin forming in parallel and then to combine in pairs, it would seem that perhaps this would allow for sublinear assembly times. However, Chen and Doty [1] developed a physically inspired timing model for the 2HAM (referred to there as the Hierarchical aTAM) and showed that it is impossible to build shapes of diameter \(n\) in time less than \(\Omega(n)\) in deterministic systems under that timing model. Nonetheless, they then exhibited a nondeterministic system which can assemble an n × n' rectangle (where n > n' ) in time \(O(n^{4/5}\log n)\), breaking the linear-time lower bound (which applies not only to deterministic 2HAM systems, but also to seeded aTAM systems as mentioned in Speed of assembly).

References

  1. Ho-Lin Chen, David Doty - Parallelism and Time in Hierarchical Self-Assembly
    SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1163--1182,2012
    Bibtex
    Author : Ho-Lin Chen, David Doty
    Title : Parallelism and Time in Hierarchical Self-Assembly
    In : SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms -
    Address :
    Date : 2012