Difference between revisions of "Open Problems"
| Line 8: | Line 8: | ||
<br> | <br> | ||
<br> | <br> | ||
| − | 3) | + | 3) In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic Universality | intrinsically universal]] for itself, but for [[Directed Tile Assembly Systems | directed]] systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems intrinsically universal for itself? |
| Line 53: | Line 53: | ||
booktitle = "Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)", | booktitle = "Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)", | ||
pages = "417--426" | pages = "417--426" | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name =USA><bibtex> | ||
| + | @inproceedings{USA, | ||
| + | author = "David Doty and Jack H. Lutz and Matthew J. Patitz and Scott M. Summers and Damien Woods", | ||
| + | title = "Intrinsic Universality in Self-Assembly", | ||
| + | booktitle = "Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science", | ||
| + | year = 2009, | ||
| + | pages = "275--286" | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name =IUSA><bibtex> | ||
| + | @inproceedings{IUSA, | ||
| + | author = {David Doty and | ||
| + | Jack H. Lutz and | ||
| + | Matthew J. Patitz and | ||
| + | Robert T. Schweller and | ||
| + | Scott M. Summers and | ||
| + | Damien Woods}, | ||
| + | title = {The tile assembly model is intrinsically universal}, | ||
| + | booktitle = {Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science}, | ||
| + | series = {FOCS 2012}, | ||
| + | year = {2012}, | ||
| + | location = {New Brunswick, New Jersey}, | ||
} | } | ||
</bibtex></ref> | </bibtex></ref> | ||
Revision as of 10:49, 27 May 2014
The following are a list of open problems in self-assembly:
1) In his 1998 thesis [1], Winfree showed that the class of directed aTAM systems at temperature 2 is computationally universal, and in [2] Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty and that in 2 planes directed aTAM temperature 1 systems were computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In [3] Doty, Patitz, and Summers provide deep insights into this question.
2) In [4], Doty et al. introduced a model known as the fuzzy temperature model and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?
3) In [5] Doty et al. showed that the aTAM is intrinsically universal for itself, but for directed systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed aTAM systems intrinsically universal for itself?
References
- ↑
Erik Winfree - Algorithmic Self-Assembly of DNA
- Ph.D. Thesis, California Institute of Technology , June 1998
- BibtexAuthor : Erik Winfree
Title : Algorithmic Self-Assembly of DNA
In : Ph.D. Thesis, California Institute of Technology -
Address :
Date : June 1998
- ↑
Matthew Cook, Yunhui Fu, Robert T. Schweller - Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
- SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms ,2011
- BibtexAuthor : Matthew Cook, Yunhui Fu, Robert T. Schweller
Title : Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
In : SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms -
Address :
Date : 2011
- ↑
David Doty, Matthew J. Patitz, Scott M. Summers - Limitations of Self-Assembly at Temperature 1
- Theoretical Computer Science 412:145-158,2011
- BibtexAuthor : David Doty, Matthew J. Patitz, Scott M. Summers
Title : Limitations of Self-Assembly at Temperature 1
In : Theoretical Computer Science -
Address :
Date : 2011
- ↑
David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers - Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
- Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) pp. 417--426,2010
- BibtexAuthor : David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers
Title : Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
In : Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) -
Address :
Date : 2010
- ↑
David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods - The tile assembly model is intrinsically universal
- Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science ,2012
- BibtexAuthor : David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods
Title : The tile assembly model is intrinsically universal
In : Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science -
Address :
Date : 2012
Cite error: <ref> tag with name "USA" defined in <references> is not used in prior text.
