Difference between revisions of "Open Problems"
Jump to navigation
Jump to search
| Line 2: | Line 2: | ||
<br> | <br> | ||
<br> | <br> | ||
| − | + | <ul> | |
| − | < | + | |
| − | < | + | <li>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. They also showed that in 2 planes directed aTAM temperature 1 systems are 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.</li> |
| − | + | ||
| − | < | + | <li>In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[Fuzzy Temperature Fault Tolerance | 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?</li> |
| − | < | + | |
| − | + | <li>In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic universality of the aTAM | 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?</li> | |
| − | < | + | |
| − | < | + | <li>Is the [[STAM]] [[Intrinsic Universality in the 2HAM | intrinsically universal]] for itself? In <ref name=STAMIU /> it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM.</li> |
| − | + | ||
| − | < | + | <li>Is the class of [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 1 [[Intrinsic universality of the aTAM | intrinsically universal]] for itself?</li> |
| − | < | + | |
| − | + | <li>In his 1998 thesis <ref name=Winf98 />, Winfree introduced both the [[Abstract Tile Assembly Model (aTAM) | aTAM]] and its more practical counterpart the [[Kinetic Tile Assembly Model (kTAM) | kTAM]]. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.</li> | |
| − | < | + | |
| − | < | + | <li>In [[Self-Assembly of Discrete Self-Similar Fractals]], Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the [[Abstract Tile Assembly Model (aTAM) | aTAM]].</li> |
| − | |||
| − | < | ||
| − | < | ||
| − | |||
| Line 81: | Line 77: | ||
year = {2012}, | year = {2012}, | ||
location = {New Brunswick, New Jersey}, | location = {New Brunswick, New Jersey}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name =STAMIU><bibtex> | ||
| + | @inproceedings{DBLP:conf/dna/HendricksPPR13, | ||
| + | author = {Jacob Hendricks and | ||
| + | Jennifer E. Padilla and | ||
| + | Matthew J. Patitz and | ||
| + | Trent A. Rogers}, | ||
| + | title = {Signal Transmission across Tile Assemblies: 3D Static Tiles | ||
| + | Simulate Active Self-assembly by 2D Signal-Passing Tiles}, | ||
| + | booktitle = {DNA Computing and Molecular Programming - 19th International | ||
| + | Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013. | ||
| + | Proceedings}, | ||
| + | year = {2013}, | ||
| + | pages = {90-104}, | ||
| + | ee = {http://dx.doi.org/10.1007/978-3-319-01928-4_7}, | ||
| + | bibsource = {DBLP, http://dblp.uni-trier.de} | ||
} | } | ||
</bibtex></ref> | </bibtex></ref> | ||
Revision as of 17:58, 27 May 2014
The following are a list of open problems in self-assembly:
- 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. They also showed that in 2 planes directed aTAM temperature 1 systems are 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.
- 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?
- 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?
- Is the STAM intrinsically universal for itself? In [6] it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM.
- Is the class of aTAM systems at temperature 1 intrinsically universal for itself?
- In his 1998 thesis [1], Winfree introduced both the aTAM and its more practical counterpart the kTAM. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.
- In Self-Assembly of Discrete Self-Similar Fractals, Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the aTAM.
- ↑ 1.0 1.1
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
- ↑
Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, Trent A. Rogers - Signal Transmission across Tile Assemblies: 3D Static Tiles
Simulate Active Self-assembly by 2D Signal-Passing Tiles
- DNA Computing and Molecular Programming - 19th International Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013. Proceedings pp. 90-104,2013
- BibtexAuthor : Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, Trent A. Rogers
Title : Signal Transmission across Tile Assemblies: 3D Static TilesSimulate Active Self-assembly by 2D Signal-Passing Tiles
Proceedings -
In : DNA Computing and Molecular Programming - 19th International Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013.
Address :
Date : 2013
