MURAL - Maynooth University Research Archive Library



    The program-size complexity of self-assembled paths


    Meunier, Pierre-Étienne, Regnault, Damien and Woods, Damien (2020) The program-size complexity of self-assembled paths. STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pp. 727-737.

    [thumbnail of DW_the program-size.pdf]
    Preview
    Text
    DW_the program-size.pdf

    Download (344kB) | Preview

    Abstract

    We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theory suggests, and our result proves, that small differences in the nature of adhesive bindings between abstract square molecules gives rise to vastly different expressive capabilities. In the cooperative abstract Tile Assembly Model, square tiles attach to each other using multi-sided cooperation of one, two or more sides. This precise control of tile binding is directly exploited for algorithmic tasks including growth of specified shapes using very few tile types, as well as simulation of Turing machines and even self-simulation of self-assembly systems. But are cooperative bindings required for these computational tasks? The definitionally simpler noncooperative (or Temperature 1) model has poor control over local binding events: tiles stick if they bind on at least one side. This has led to the conjecture that it is impossible for it to exhibit precisely controlled growth of computationally-defined shapes. Here, we prove such an impossibility result. We show that any planar noncooperative system that attempts to grow large algorithmically-controlled tile-efficient assemblies must also grow infinite non-algorithmic (pumped) structures with a simple closed-form description, or else suffer blocking of intended algorithmic structures. Our result holds for both directed and nondirected systems, and gives an explicit upper bound of (8|T|)4|T|+1(5|σ| + 6), where |T| is the size of the tileset and |σ| is the size of the seed assembly, beyond which any path of tiles is pumpable or blockable.
    Item Type: Article
    Keywords: Self-assembly; tilings; pumping lemma; DNA computing;
    Academic Unit: Assisting Living & Learning,ALL institute
    Faculty of Science and Engineering > Electronic Engineering
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15712
    Identification Number: 10.1145/3357713.3384263
    Depositing User: Damien Woods
    Date Deposited: 22 Mar 2022 14:31
    Journal or Publication Title: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
    Publisher: ACM Digital Library
    Refereed: Yes
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/15712
    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