Complex Systems and Computing
– Self-assembly

Self-assembly is the process by which small components (e.g. molecules) autonomously come together to form more complex structures. It is considered a promising technique in nano-technology for building miniature size devices. Molecular computation uses self-assembly to solve computational problems. A mathematical theory of self-assembly based on Wang tiles was proposed by E.Winfree in his Ph.D thesis in 1998. Our group has expertise both in Wang tiles and in molecular computing, so it is quite natural for the group to study Winfree's model. For example, we participated in

• L.Adleman, J.Kari, L.Kari and D.Reishus. On the decidability of self-assembly of infinite ribbons. In: Proceedings of FOCS'2002, 43rd Annual Symposium on Foundations of Computer Science, 530-537, 2002

to settle a decade old snake-tiling problem, proving that unbounded growth in self-assembly is undecidable. Recently we have been interested in the tiling problems using deterministic tiles, where each tile is uniquely determined by a small number of its neighbors. Motivation to this study stems originally from questions concerning cellular automata, but also applications in the mathematical theory of self-assembly are possible.