The need for seed (in the abstract Tile Assembly Model)

DOI10.1007/S00453-023-01160-WMaRDI QIDQ6185943zbMATH OpenOpenAlexFDO

Authors Matthew J. Patitz

Publication date 9 January 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.03877

zbMATH Keywords

algorithmic self-assemblysimulationtile assembly modeltile complexity

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Abstract: In the abstract Tile Assembly Model (aTAM) square tiles self-assemble, autonomously binding via glues on their edges, to form structures. Algorithmic aTAM systems can be designed in which the patterns of tile attachments are forced to follow the execution of targeted algorithms. Such systems have been proven to be computationally universal as well as intrinsically universal (IU), a notion borrowed and adapted from cellular automata showing that a single tile set exists which is capable of simulating all aTAM systems (FOCS 2012). The input to an algorithmic aTAM system can be provided in a variety of ways, with a common method being via the "seed" assembly, which is a pre-formed assembly from which all growth propagates. In this paper we present a series of results which investigate the the trade-offs of using seeds consisting of a single tile, versus those containing multiple tiles. We show that arbitrary systems with multi-tile seeds cannot be converted to functionally equivalent systems with single-tile seeds without using a scale factor > 1. We prove tight bounds on the scale factor required, and also present a construction which uses a large scale factor but an optimal number of unique tile types. That construction is then used to develop a construction that performs simultaneous simulation of all aTAM systems in parallel, as well as to display a connection to other tile-based self-assembly models via the notion of intrinsic universality.

Cites work

• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• Intrinsic universality in tile self-assembly requires cooperation
• On the effects of hierarchical self-assembly for reducing program-size complexity
• One tile to rule them all: simulating any tile assembly system with a single universal tile
• Randomized Self-assembly for Approximate Shapes
• Randomized self-assembly for exact shapes
• Reducing tile complexity for self-assembly through temperature programming
• Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
• Running time and program size for self-assembled squares
• Self-assembly of discrete self-similar fractals
• Self-assembly with geometric tiles
• Strict self-assembly of discrete Sierpinski triangles
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• The power of duples (in self-assembly): it's not so hip to be square
• The program-size complexity of self-assembled squares (extended abstract)
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• The two-handed tile assembly model is not intrinsically universal
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly

This page was built for publication: The need for seed (in the abstract Tile Assembly Model)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185943)