MURAL - Maynooth University Research Archive Library

    One tile to rule them all: Simulating any tile assembly system with a single universal tile

    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

    Download (18MB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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
    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)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads