Verification of aTAM systems

From self-assembly wiki
Revision as of 19:23, 10 July 2013 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

Several "verification problems" (answering the question of whether or not a given system has a specific property) have been studied in relation to the aTAM, and characterized by their complexity. Among them are:

\begin{enumerate} 

   \item Does aTAM system \(\mathcal{T}\) uniquely produce a given assembly?  This was shown to require time polynomial in the size of the assembly and tile set by Adleman, et al. in [1].
   \item Does aTAM system \(\calT\) uniquely produce a given shape?  This was shown to be in co-NP-complete for temperature 1 by Cannon, et al. in \cite{Versus} and co-NP-complete for temperature 2 in [2] by Cheng, et al.
   \item Is a given assembly terminal in aTAM system \(\mathcal{T}\)?  This was shown to require time linear in the size of the assembly and tile set in Cite error: Closing </ref> missing for <ref> tag

[2]

[3]

[2]

[4]

</references>

  1. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named ACGHKMR02
  2. ↑ 2.0 2.1 2.2 Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es - Complexities for Generalized Models of Self-Assembly
    SIAM Journal on Computing 34:1493--1515,2005
    Bibtex
    Author : Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es
    Title : Complexities for Generalized Models of Self-Assembly
    In : SIAM Journal on Computing -
    Address :
    Date : 2005
    Cite error: Invalid <ref> tag; name "AGKS05g" defined multiple times with different content
  3. ↑ Leonard Adleman, Qi Cheng, Ashish Goel,, Ming-Deh Huang - Running time and program size for self-assembled squares
    pp. 740--748,2001
    Bibtex
    Author : Leonard Adleman, Qi Cheng, Ashish Goel,, Ming-Deh Huang
    Title : Running time and program size for self-assembled squares
    In : -
    Address :
    Date : 2001
  4. ↑ Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow - Two Hands Are Better Than One (up to constant factors)
    Technical Report, Computing Research Repository (1201.1650),2012
    http://arxiv.org/abs/1201.1650
    Bibtex
    Author : Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow
    Title : Two Hands Are Better Than One (up to constant factors)
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2012
Retrieved from "http://self-assembly.net/wiki/index.php?title=Verification_of_aTAM_systems&oldid=830"