Self-Assembly of Patterns in the abstract Tile Assembly Model

2024/02/26 by Phillip Drake, Matthew J. Patitz, Drake, Phillip +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Archaeology #Cellular Automata and Applications #Computer science #DNA and Biological Computing #Geography #Modular Robots and Swarm Intelligence #Tile

paper · pdf · doi:10.48550/arxiv.2402.16284

openalex publication_date 2024/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the abstract Tile Assembly Model, self-assembling systems consisting of tiles of different colors can form structures on which colored patterns are ``painted.'' We explore the complexity, in terms of the numbers of unique tile types required, of assembling various patterns. We first demonstrate how to efficiently self-assemble a set of simple patterns, then show tight bounds on the tile type complexity of self-assembling 2-colored patterns on the surfaces of square assemblies. Finally, we demonstrate an exponential gap in tile type complexity of self-assembling an infinite series of patterns between systems restricted to one plane versus those allowed two planes.

Related

• Self-Assembly with Geometric Tiles
• 3-color Bounded Patterned Self-assembly
• The Complexity of Fixed-Height Patterned Tile Self-Assembly
• Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes
• One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly\n System, or Tiling System with a Single Puzzle Piece