Demaine, Erik D. and Demaine, Martin L. and Sandor, Fekete P and Patitz, Mathhew J. and Schweller, Robert and Winslow, Andrew and Woods, Damien (2014) One tile to rule them all: Simulating any tile assembly system with a single universal tile. Lecture Notes in Computer Science. pp. 368-379. ISSN 0302-9743

Preview

Download (18MB) | Preview

Abstract

In the classical model of tile self-assembly, unit square tiles translate in the plane and attach edgewise to form large crystalline structures. This model of self-assembly has been shown to be capable of asymptotically optimal assembly of arbitrary shapes and, via information-theoretic arguments, increasingly complex shapes necessarily require increasing numbers of distinct types of tiles. We explore the possibility of complex and efficient assembly using systems consisting of a single tile. Our main result shows that any system of square tiles can be simulated using a system with a single tile that is permitted to flip and rotate. We also show that systems of single tiles restricted to translation only can simulate cellular automata for a limited number of steps given an appropriate seed assembly, and that any longer-running simulation must induce infinite assembly.

Item Type:	Article
Keywords:	DNA computing; algorithmic self-assembly; hexagonal tiles;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	15716
Depositing User:	Damien Woods
Date Deposited:	22 Mar 2022 15:18
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer Verlag
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads