Name
Title | ||
|---|---|---|
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile. |
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. |
Year | Venue | Keywords |
|---|---|---|
2014 | Lecture Notes in Computer Science | DNA computing,algorithmic self-assembly,hexagonal tiles |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Computer science,Unit square,Asymptotically optimal algorithm,Tile,DNA computing | Conference | 8572 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.45 |
References | Authors | |
6 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Martin L. Demaine | 2 | 592 | 84.37 |
| Sándor P. Fekete | 3 | 1931 | 179.96 |
| Matthew J. Patitz | 4 | 435 | 31.04 |
| Robert T. Schweller | 5 | 627 | 40.05 |
| Andrew Winslow | 6 | 91 | 15.29 |
| Damien Woods | 7 | 373 | 25.23 |