Difference between revisions of "Speed of Assembly in the 2HAM"
(Created page with "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...") |
m (moved Speed of Assembly to Speed of Assembly in the 2HAM) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 17: | Line 17: | ||
[[Category: 2HAM Results]] | [[Category: 2HAM Results]] | ||
| + | [[Category:Self-assembly]] | ||
Latest revision as of 14:58, 27 May 2014
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
- ↑
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
- BibtexAuthor : 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
