View source for Verification of aTAM systems

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:

    1) 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 />.
    2) 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.
    3) 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>
    4) 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}

==References==
<references>

<ref name =ACGHKMR02><bibtex>
@inproceedings{ACGHKMR02,
  author =   "Leonard M. Adleman and Qi Cheng and Ashish Goel and Ming-Deh A. Huang and David Kempe and Pablo Moisset de Espan\'{e}s and Paul W. K. Rothemund",
  title =    "Combinatorial optimization problems in self-assembly",
  booktitle = "Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing",
  year = 2002,
  pages = "23--32"
}
</bibtex></ref>

<ref name =AGKS05g><bibtex>
@article{AGKS05g,
  author =	"Qi Cheng and Gagan Aggarwal and Michael H. Goldwasser and Ming-Yang Kao and Robert T. Schweller and Pablo Moisset de Espan\'{e}s",
  title =	"Complexities for Generalized Models of Self-Assembly",
  journal =	"SIAM Journal on Computing",
  volume = "34",
  pages = 	"1493--1515",
  year =	"2005",
}
</bibtex></ref>

<ref name =AdChGoHu01><bibtex>
@article{AdChGoHu01,
  author =      "Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang",
  year =        "2001",
  title =       "Running time and program size for self-assembled squares",
  booktitle = "Proceedings of the 33rd Annual ACM Symposium on Theory of Computing",
  publisher = "ACM"
  pages     = {740--748}
}
</bibtex></ref>

<ref name =AGKS05g><bibtex>
@article{AGKS05g,
  author =      "Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, and Pablo Moisset de Espan&eacute;s",
  year =        "2005",
  title =       "Complexities for generalized models of self-assembly",
  journal = "SIAM Journal on Computing",
  volume = "34",
  pages     = {1493--1515}
}
</bibtex></ref>

<ref name =Versus><bibtex>
@techreport{Versus,
  author = "Sarah Cannon and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Matthew J. Patitz and Robert Schweller and Scott M. Summers and Andrew Winslow",
  title = "Two Hands Are Better Than One (up to constant factors)",
  number = "1201.1650",
  institution = "Computing Research Repository",
  year = 2012,
  url = "http://arxiv.org/abs/1201.1650"
}
</bibtex></ref>

</references>

[[Category:Results in the aTAM]]