Identifying Shapes Using Self-assembly (Extended Abstract)

被引：0
作者：
Patitz, Matthew J. [1 ]
Summers, Scott M. [2 ]
机构：
[1] Univ Texas Pan Amer, Dept Comp Sci, Edinburg, TX 78539 USA
[2] Univ Wisconsin, Platteville, WI 53818 USA
来源：
ALGORITHMS AND COMPUTATION, PT 2 | 2010年 / 6507卷
关键词：
DNA;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape-drawn from a very general class of shapes-matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.
引用
收藏
页码：458 / +
页数：3
相关论文
共 26 条
  • [1] Abel Z, 2010, PROC APPL MATH, V135, P1045
  • [2] Adleman L., 2001, 6 INT C DIFF EQ APPL
  • [3] Adleman L. M., 2000, 00722 U SO CAL
  • [4] Complexities for generalized models of self-assembly
    Aggarwal, G
    Cheng, Q
    Goldwasser, MH
    Kao, MY
    De Espanes, PM
    Schweller, RT
    [J]. SIAM JOURNAL ON COMPUTING, 2005, 34 (06) : 1493 - 1515
  • [5] Self-assembly of a nanoscale DNA box with a controllable lid
    Andersen, Ebbe S.
    Dong, Mingdong
    Nielsen, Morten M.
    Jahn, Kasper
    Subramani, Ramesh
    Mamdouh, Wael
    Golas, Monika M.
    Sander, Bjoern
    Stark, Holger
    Oliveira, Cristiano L. P.
    Pedersen, Jan Skov
    Birkedal, Victoria
    Besenbacher, Flemming
    Gothelf, Kurt V.
    Kjems, Jorgen
    [J]. NATURE, 2009, 459 (7243) : 73 - U75
  • [6] An information-bearing seed for nucleating algorithmic self-assembly
    Barish, Robert D.
    Schulman, Rebecca
    Rothemund, Paul W. K.
    Winfree, Erik
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2009, 106 (15) : 6054 - 6059
  • [7] Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues
    Erik D. Demaine
    Martin L. Demaine
    Sándor P. Fekete
    Mashhood Ishaque
    Eynat Rafalin
    Robert T. Schweller
    Diane L. Souvaine
    [J]. Natural Computing, 2008, 7 (3) : 347 - 370
  • [8] Fu Y., 2011, P ACM SIAM IN PRESS
  • [9] A proximity-based programmable DNA nanoscale assembly line
    Gu, Hongzhou
    Chao, Jie
    Xiao, Shou-Jun
    Seeman, Nadrian C.
    [J]. NATURE, 2010, 465 (7295) : 202 - U86
  • [10] Self-assembly and mineralization of peptide-amphiphile nanofibers
    Hartgerink, JD
    Beniash, E
    Stupp, SI
    [J]. SCIENCE, 2001, 294 (5547) : 1684 - 1688
123