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., 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

    [thumbnail of DW_one tile.pdf]
    Preview
    Text
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads