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 条
  • [31] Nondeterministic self-assembly of two tile types on a lattice
    Tesoro, S.
    Ahnert, S. E.
    PHYSICAL REVIEW E, 2016, 93 (04)
  • [32] Solving the Assignment Problem by Algorithmic Tile Self-Assembly
    Cheng, Zhen
    Xiao, Jianhua
    NANOSCIENCE AND NANOTECHNOLOGY LETTERS, 2012, 4 (12) : 1132 - 1139
  • [33] A Graph Model for Tile Sets in DNA Self-Assembly
    Aran, Zahra Mashreghian
    Hashempour, Masoud
    Lorubardi, Fabrizio
    IEEE INTERNATIONAL WORKSHOP ON DESIGN AND TEST OF NANO DEVICES, CIRCUITS AND SYSTEMS, PROCEEDINGS, 2008, : 77 - 80
  • [34] A 'tile' tale: Hierarchical self-assembly of DNA lattices
    Chandrasekaran, Arun Richard
    Zhuo, Rebecca
    APPLIED MATERIALS TODAY, 2016, 2 : 7 - 16
  • [35] Optimizing Tile Concentrations to Minimize Errors and Time for DNA Tile Self-assembly Systems
    Chen, Ho-Lin
    Kao, Ming-Yang
    DNA COMPUTING AND MOLECULAR PROGRAMMING, 2011, 6518 : 13 - +
  • [36] Programmable DNA tile self-assembly using a hierarchical sub-tile strategy
    Shi, Xiaolong
    Lu, Wei
    Wang, Zhiyu
    Pan, Linqiang
    Cui, Guangzhao
    Xu, Jin
    LaBean, Thomas H.
    NANOTECHNOLOGY, 2014, 25 (07)
  • [37] DNA tile based self-assembly: Building complex nanoarchitectures
    Lin, Chenxiang
    Liu, Yan
    Rinker, Sherri
    Yan, Hao
    CHEMPHYSCHEM, 2006, 7 (08) : 1641 - 1647
  • [38] Search methods for tile sets in patterned DNA self-assembly
    Goos, Mika
    Lempiainen, Tuomo
    Czeizler, Eugen
    Orponen, Pekka
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2014, 80 (01) : 297 - 319
  • [39] The Complexity of Fixed-Height Patterned Tile Self-Assembly
    Seki, Shinnosuke
    Winslow, Andrew
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2017, 28 (05) : 465 - 482
  • [40] Proofreading tile sets: Error correction for algorithmic self-assembly
    Winfree, E
    Bekbolatov, R
    DNA COMPUTING, 2004, 2943 : 126 - 144
12345