Self-assembly of Patterns in the Abstract Tile Assembly Model

被引:1
作者
Drake, Phillip [1 ]
Patitz, Matthew J. [1 ]
Summers, Scott M. [2 ]
Tracy, Tyler [1 ]
机构
[1] Univ Arkansas, Fayetteville, AR 72701 USA
[2] Univ Wisconsin Oshkosh, Oshkosh, WI 54901 USA
来源
UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2024 | 2024年 / 14776卷
关键词
DNA; COMPLEXITY;
D O I
10.1007/978-3-031-63742-1_7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:89 / 103
页数:15
相关论文
共 21 条
[1]  
Adleman L., 2001, P 33 ANN ACM S THEOR, P740, DOI DOI 10.1145/380752.380881
[2]  
Czeizler Eugen, 2012, DNA Computing and Molecular Programming. Proceedings 18th International Conference, DNA 18, P58, DOI 10.1007/978-3-642-32208-2_5
[3]  
Doty D., 2023, Leibniz International Proceedings in Informatics (LIPIcs), V276
[4]  
Drake P, 2024, Pattern self-assembly software
[5]  
Drake P, 2024, Arxiv, DOI arXiv:2402.16284
[6]  
Evans C., 2014, Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly
[7]  
Hader D, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P2607
[8]   Binary Pattern Tile Set Synthesis Is NP-Hard [J].
Kari, Lila ;
Kopecki, Steffen ;
Meunier, Pierre-Etienne ;
Patitz, Matthew J. ;
Seki, Shinnosuke .
ALGORITHMICA, 2017, 78 (01) :1-46
[9]   Computability and Complexity in Self-assembly [J].
Lathrop, James I. ;
Lutz, Jack H. ;
Patitz, Matthew J. ;
Summers, Scott M. .
THEORY OF COMPUTING SYSTEMS, 2011, 48 (03) :617-647
[10]   Strict self-assembly of discrete Sierpinski triangles [J].
Lathrop, James I. ;
Lutz, Jack H. ;
Summers, Scott M. .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (4-5) :384-405