Abstract
Self-assembling tile systems are a model for assembling DNA-based nano artefacts. In the currently known constructions, most of the effort is put on garanteeing the size of the output object, whereas the geometrical efficiency of the assembling of the shape itself is left aside. We propose in this paper a framework to obtain provably time efficient self-assembling tile systems. Our approach consists in studying how the flow of information has to circulate within the desired shape to guarantee an optimal time construction. We show how this study can yield an adequate ordering of the tiling process from which one can deduced a provably time efficient tile systems for that shape. We apply our framework to squares and cubes for which we obtain time optimal self-assembling tile systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M., Cheng, Q., Goel, A., Huang, M.-D.A.: Running time and program size for self-assembled squares. In: STOC 2001: Proc. of the 33rd ACM symposium on Theory of computing, pp. 740–748 (2001)
Becker, F., Rapaport, I., Rémila, E.: Self-assemblying classes of shapes with a minimum number of tiles, and in optimal time. In: LNCS Proc. of Found. of Software Tech. and Theo. Comp. Sci., pp. 45–56 (2006)
Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (2002)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC 2000: Proceedings of the 32nd symp. on Theory of computing, pp. 459–468 (2000)
Rothemund, P.W.K.: Theory and Experiments in Algorithmic Self-Assembly. PhD thesis, University of Southern California (2001)
Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 344–354. Springer, Heidelberg (2005)
Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, Caltech (1998)
Winfree, E.: Simulations of computing by self-assembly. In: Proceedings of the Fourth DIMACS Meeting on DNA Based Computing, pp. 213–242 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Becker, F., Rémila, É., Schabanel, N. (2009). Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes. In: Goel, A., Simmel, F.C., Sosík, P. (eds) DNA Computing. DNA 2008. Lecture Notes in Computer Science, vol 5347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03076-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-03076-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03075-8
Online ISBN: 978-3-642-03076-5
eBook Packages: Computer ScienceComputer Science (R0)