Difference between revisions of "Verification of aTAM systems"
Jump to navigation
Jump to search
(Created page with "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 ...") |
|||
| Line 2: | Line 2: | ||
\begin{enumerate} | \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 | + | \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 <ref name=ACGHKMR02 />. |
| − | \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 | + | \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 <ref name=AGKS05g /> by Cheng, et al. |
| − | \item Is a given assembly terminal in aTAM system $\ | + | \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 <ref name=ACGHKMR02> |
| − | \item Given an aTAM system $\calT$, does it produce a finite terminal assembly? An infinite terminal assembly? These were both shown to be uncomputable in | + | \item Given an aTAM system $\calT$, does it produce a finite terminal assembly? An infinite terminal assembly? These were both shown to be uncomputable in <ref name=Versus />. |
\end{enumerate} | \end{enumerate} | ||
Revision as of 19:23, 10 July 2013
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
</references>
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedACGHKMR02 - ↑ 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
- BibtexAuthor : 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
<ref>tag; name "AGKS05g" defined multiple times with different content - ↑
Leonard Adleman, Qi Cheng, Ashish Goel,, Ming-Deh Huang - Running time and program size for self-assembled squares
- ↑
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
BibtexAuthor : 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
