A Caltech Library Service

One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile

Demaine, Erik D. and Demaine, Martin L. and Fekete, Sándor P. and Patitz, Matthew J. and Schweller, Robert T. and Winslow, Andrew and Woods, Damien (2014) One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile. In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Lecture Notes in Computer Science. No.8572. Springer , Berlin, Germany, pp. 368-379. ISBN 978-3-662-43948-7.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2014 Springer-Verlag Berlin Heidelberg. Research of Matthew J. Patitz supported in part by NSF grant CCF-1117672. Research of Robert Schweller supported in part by NSF grant CCF-1117672. Research of Andrew Winslow supported in part by NSF grant CDI-0941538. Research of Damien Woods Supported by NSF grants 0832824 & 1317694 (the Molecular Programming Project), CCF-1219274, and CCF-1162589. This work was initiated at the 27th Bellairs Winter Workshop on Computational Geometry held on February 11-17, 2012 in Holetown, Barbados. We thank the other participants of that workshop for a fruitful and collaborative environment. In particular, we thank Brad Ballinger and Anna Lubiw for important discussions regarding Lemma 3. In addition, we thank Jarkko Kari for interesting and fruitful discussions on aperiodic tilings of the plane with few tile types.
Funding AgencyGrant Number
Subject Keywords:DNA computing, algorithmic self-assembly, hexagonal tiles
Series Name:Lecture Notes in Computer Science
Issue or Number:8572
Record Number:CaltechAUTHORS:20150512-112419135
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:57453
Deposited By: Ruth Sustaita
Deposited On:12 May 2015 19:03
Last Modified:20 Nov 2019 22:51

Repository Staff Only: item control page