Difference between revisions of "Open Problems"
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
The following are a list of open problems in self-assembly: | The following are a list of open problems in self-assembly: | ||
<br> | <br> | ||
| − | 1) In his 1998 thesis <ref name=Winf98 />, Winfree showed that the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 2 is computationally universal, and in <ref name=CooFuSch11/> Cook et | + | 1) In his 1998 thesis <ref name=Winf98 />, Winfree showed that the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 2 is computationally universal, and in <ref name=CooFuSch11/> 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 <ref name=jLSAT1 /> Doty, Patitz, and Summers provide deep insights into this question. |
| + | <br> | ||
| + | 2) In <ref name = SFTSAFT/>, Doty et al. | ||
| Line 36: | Line 38: | ||
booktitle = {SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms}, | booktitle = {SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms}, | ||
publisher = {SIAM}, | publisher = {SIAM}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name =SFTSAFT><bibtex> | ||
| + | @inproceedings{SFTSAFT, | ||
| + | author = "David Doty and Matthew J. Patitz and Dustin Reishus and Robert T. Schweller and Scott M. Summers", | ||
| + | title = "Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature", | ||
| + | year = 2010, | ||
| + | booktitle = "Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)", | ||
| + | pages = "417--426" | ||
} | } | ||
</bibtex></ref> | </bibtex></ref> | ||
Revision as of 10:18, 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.
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
