Verification in staged tile self-assembly

被引：3
|
作者：
Schweller, Robert [1 ]
Winslow, Andrew [1 ]
Wylie, Tim [1 ]
机构：
[1] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA
来源：
NATURAL COMPUTING | 2019年 / 18卷 / 01期
基金：
美国国家科学基金会;
关键词：
DNA computing; Biocomputing; 2HAM; Hierarchical;
D O I：
10.1007/s11047-018-9701-2
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are coNP(NP)-hard and contained in PSPACE (and in II2sP for staged systems with s stages). En route, we prove that unique shape verification problem in the 2HAM is coNP(NP)-complete.
引用
收藏
页码：107 / 117
页数：11
相关论文
共 50 条
  • [1] Verification in staged tile self-assembly
    Robert Schweller
    Andrew Winslow
    Tim Wylie
    Natural Computing, 2019, 18 : 107 - 117
  • [2] Verification in Staged Tile Self-Assembly
    Schweller, Robert
    Winslow, Andrew
    Wylie, Tim
    UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2017, 2017, 10240 : 98 - 112
  • [3] Distributed agreement in tile self-assembly
    Aaron Sterling
    Natural Computing, 2011, 10 : 337 - 355
  • [4] Smart Tile Self-Assembly and Replication
    Kari, Lila
    Simjour, Amirhossein
    FUNDAMENTA INFORMATICAE, 2017, 154 (1-4) : 239 - 260
  • [5] Distributed agreement in tile self-assembly
    Sterling, Aaron
    NATURAL COMPUTING, 2011, 10 (01) : 337 - 355
  • [6] Distributed Agreement in Tile Self-assembly
    Sterling, Aaron
    DNA COMPUTING AND MOLECULAR PROGRAMMING, 2009, 5877 : 154 - 163
  • [7] Triangular Tile Self-assembly Systems
    Kari, Lila
    Seki, Shinnosuke
    Xu, Zhi
    DNA COMPUTING AND MOLECULAR PROGRAMMING, 2011, 6518 : 89 - 99
  • [8] Self-assembly of Patterns in the Abstract Tile Assembly Model
    Drake, Phillip
    Patitz, Matthew J.
    Summers, Scott M.
    Tracy, Tyler
    UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION, UCNC 2024, 2024, 14776 : 89 - 103
  • [9] Staged Self-Assembly of Colloidal Metastructures
    Chen, Qian
    Bae, Sung Chul
    Granick, Steve
    JOURNAL OF THE AMERICAN CHEMICAL SOCIETY, 2012, 134 (27) : 11080 - 11083
  • [10] Self-replication via tile self-assembly
    Alseth, Andrew
    Hader, Daniel
    Patitz, Matthew J.
    NATURAL COMPUTING, 2024, 23 (03) : 497 - 530
12345