Difference between revisions of "Speed of assembly"
(Created page with "An important efficiency measure is tile complexity. However, another interesting and important measure which has been investigated is the speed at which an assembly can form, or...") |
|||
| Line 1: | Line 1: | ||
An important efficiency measure is tile complexity. However, another interesting and important measure which has been investigated is the speed at which an assembly can form, or the number of assembly steps required by a system to reach the final, desired target structure. Of course, in the basic aTAM where each step of assembly consists of a single tile addition, the assembly time for a shape consisting of ''n'' points cannot vary, and is fixed at ''n - s'' steps (where ''s'' is the number of tiles in the seed, usually ''1''). However, by considering slight variants of the model, such as a version where at each time step all tiles which are able to individually attach do so, the assembly time becomes variable and an interesting metric. | An important efficiency measure is tile complexity. However, another interesting and important measure which has been investigated is the speed at which an assembly can form, or the number of assembly steps required by a system to reach the final, desired target structure. Of course, in the basic aTAM where each step of assembly consists of a single tile addition, the assembly time for a shape consisting of ''n'' points cannot vary, and is fixed at ''n - s'' steps (where ''s'' is the number of tiles in the seed, usually ''1''). However, by considering slight variants of the model, such as a version where at each time step all tiles which are able to individually attach do so, the assembly time becomes variable and an interesting metric. | ||
| − | In < ref name=AdChGoHu01 />, Adleman, Cheng, Goel, and Huang proved that the deterministic assembly of a shape of diameter ''d'' requires time $\Omega(d)$. In <ref name=CheDot12 /> Doty and Chen showed that this bound also holds for nondeterministic systems. In <ref name=AdChGoHu01 /> they provided a matching upper bound for a construction which was able to self-assemble an ''n × n'' square and also used the optimal $O(\frac{\log n}{\log \log n})$ tile types. See [[Building n by n squares]] for more discussion of assembly time related to ''n × n'' squares. | + | In <ref name=AdChGoHu01 />, Adleman, Cheng, Goel, and Huang proved that the deterministic assembly of a shape of diameter ''d'' requires time $\Omega(d)$. In <ref name=CheDot12 /> Doty and Chen showed that this bound also holds for nondeterministic systems. In <ref name=AdChGoHu01 /> they provided a matching upper bound for a construction which was able to self-assemble an ''n × n'' square and also used the optimal $O(\frac{\log n}{\log \log n})$ tile types. See [[Building n by n squares]] for more discussion of assembly time related to ''n × n'' squares. |
Revision as of 18:31, 10 July 2013
An important efficiency measure is tile complexity. However, another interesting and important measure which has been investigated is the speed at which an assembly can form, or the number of assembly steps required by a system to reach the final, desired target structure. Of course, in the basic aTAM where each step of assembly consists of a single tile addition, the assembly time for a shape consisting of n points cannot vary, and is fixed at n - s steps (where s is the number of tiles in the seed, usually 1). However, by considering slight variants of the model, such as a version where at each time step all tiles which are able to individually attach do so, the assembly time becomes variable and an interesting metric.
In [1], Adleman, Cheng, Goel, and Huang proved that the deterministic assembly of a shape of diameter d requires time \(\Omega(d)\). In [2] Doty and Chen showed that this bound also holds for nondeterministic systems. In [1] they provided a matching upper bound for a construction which was able to self-assemble an n × n square and also used the optimal \(O(\frac{\log n}{\log \log n})\) tile types. See Building n by n squares for more discussion of assembly time related to n × n squares.
References
- ↑ 1.0 1.1
Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang - Running time and program size for self-assembled squares
- Proceedings of the 33rd Annual ACM Symposium on Theory of Computing pp. 740--748, Hersonissos, Greece,2001
- BibtexAuthor : Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang
Title : Running time and program size for self-assembled squares
In : Proceedings of the 33rd Annual ACM Symposium on Theory of Computing -
Address : Hersonissos, Greece
Date : 2001
- ↑
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
