Demaine, Erik D., Demaine, Martin L., Sandor, Fekete P, Patitz, Mathhew J., Schweller, Robert, 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
DW_one tile.pdf
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 |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/15716 |
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)
Downloads
Downloads per month over past year