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> | <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 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. | 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> | ||
<br> | <br> | ||
2) In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[fuzzy temperature model | Fuzzy Temperature Fault Tolerance]] and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation? | 2) In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[fuzzy temperature model | Fuzzy Temperature Fault Tolerance]] and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation? | ||
Revision as of 10:22, 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 Fault Tolerance and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?
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
