Difference between revisions of "Verification of aTAM systems"
(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 ...") |
(No difference)
|
Revision as of 20:21, 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 '"`UNIQ-MathJax1-QINU`"' 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 \cite{ACGHKMR02}. \item Does aTAM system '"`UNIQ-MathJax2-QINU`"' 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 \cite{AGKS05g} by Cheng, et al. \item Is a given assembly terminal in aTAM system '"`UNIQ-MathJax3-QINU`"'? This was shown to require time linear in the size of the assembly and tile set in \cite{ACGHKMR02} \item Given an aTAM system '"`UNIQ-MathJax4-QINU`"', does it produce a finite terminal assembly? An infinite terminal assembly? These were both shown to be uncomputable in \cite{Versus}. \end{enumerate}
References
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
