Document Open Access Logo

Directed Non-Cooperative Tile Assembly Is Decidable

Authors Pierre-Étienne Meunier, Damien Regnault

PDF
Thumbnail PDF

File

LIPIcs.DNA.27.6.pdf
  • Filesize: 0.73 MB
  • 21 pages

Document Identifiers

Author Details

Pierre-Étienne Meunier
  • Albédo Énergie, Le Bourget-du-Lac, France
Damien Regnault
  • IBISC, Université Évry, Université Paris-Saclay, 91025, Evry, France

Funding

  • Meunier, Pierre-Étienne: Supported by H2020-LC-SC3 award number 957823, H2020-LC-SC3 award number 953020, H2020-LC-SC3 award number 101033700, H2020-ERC award number 772766 and SFI grant 18/ERCS/5746 (this manuscript reflects only the authors' view and the European funding institutions are not responsible for any use that may be made of the information it contains).

Acknowledgements

We thank Damien Woods for his support and advice.

Cite As Get BibTex

Pierre-Étienne Meunier and Damien Regnault. Directed Non-Cooperative Tile Assembly Is Decidable. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DNA.27.6

Abstract

We provide a complete characterisation of all final states of a model called directed non-cooperative tile self-assembly, also called directed temperature 1 tile assembly, which proves that this model cannot possibly perform Turing computation. This model is a deterministic version of the more general undirected model, whose computational power is still open. Our result uses recent results in the domain, and solves a conjecture formalised in 2011. We believe that this is a major step towards understanding the full model.
Temperature 1 tile assembly can be seen as a two-dimensional extension of finite automata, where geometry provides a form of memory and synchronisation, yet the full power of these "geometric blockings" was still largely unknown until recently (note that nontrivial algorithms which are able to build larger structures than the naive constructions have been found).

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation → Models of computation
Keywords
  • Self-assembly
  • Molecular Computing
  • Models of Computation
  • Computational Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. B. Behsaz, J. Maňuch, and L. Stacho. Turing universality of step-wise and stage assembly at Temperature 1. In DNA18: Proc. of International Meeting on DNA Computing and Molecular Programming, volume 7433 of LNCS, pages 1-11. Springer, 2012. Google Scholar
  2. L. Ceze, J. Nivala, and K. Strauss. Molecular digital data storage using DNA. Nat Rev Genet, 20(8):456-466, August 2019. Google Scholar
  3. Matthew Cook, Yunhui Fu, and Robert T. Schweller. Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D. In SODA: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 570-589, 2011. Arxiv preprint: URL: https://arxiv.org/abs/0912.0027.
  4. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods. One tile to rule them all: Simulating any tile assembly system with a single universal tile. In ICALP: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, volume 8572 of LNCS, pages 368-379. Springer, 2014. Arxiv preprint: URL: https://arxiv.org/abs/1212.4756.
  5. Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods. The two-handed tile assembly model is not intrinsically universal. In ICALP: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, volume 7965 of LNCS, pages 400-412. Springer, 2013. Arxiv preprint: URL: https://arxiv.org/abs/1306.6710.
  6. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The tile assembly model is intrinsically universal. In FOCS: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 439-446. IEEE, 2012. Arxiv preprint: URL: https://arxiv.org/abs/1111.3097.
  7. David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods. Intrinsic universality in self-assembly. In STACS: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, pages 275-286, 2009. Arxiv preprint: URL: https://arxiv.org/abs/1001.0208.
  8. David Doty, Matthew J. Patitz, and Scott M. Summers. Limitations of self-assembly at temperature 1. Theoretical Computer Science, 412(1-2):145-158, 2011. Arxiv preprint: URL: https://arxiv.org/abs/0903.1857v1.
  9. Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, and Robert T. Schweller. Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. In SODA: ACM-SIAM Symposium on Discrete Algorithms, pages 148-167. SIAM, 2015. URL: http://arxiv.org/abs/1408.3351.
  10. David Furcy and Scott M Summers. Optimal self-assembly of finite shapes at temperature 1 in 3D. Algorithmica, 80(6):1909-1963, 2018. Google Scholar
  11. David Furcy, Scott M Summers, and Christian Wendlandt. New bounds on the tile complexity of thin rectangles at temperature-1. In DNA25: International Conference on DNA Computing and Molecular Programming, pages 100-119. Springer, 2019. Google Scholar
  12. Oscar Gilbert, Jacob Hendricks, Matthew J Patitz, and Trent A Rogers. Computing in continuous space with self-assembling polygonal tiles. In SODA: ACM-SIAM Symposium on Discrete Algorithms, pages 937-956. SIAM, 2016. Arxiv preprint: URL: https://arxiv.org/abs/1503.00327.
  13. Natasa Jonoska and Daria Karpenko. Active tile self-assembly, part 1: Universality at temperature 1. Int. J. Found. Comput. Sci., 25(2):141-164, 2014. URL: https://doi.org/10.1142/S0129054114500087.
  14. Ján Maňuch, Ladislav Stacho, and Christine Stoll. Two lower bounds for self-assemblies at Temperature 1. Journal of Computational Biology, 17(6):841-852, 2010. Google Scholar
  15. Pierre-Étienne Meunier. Non-cooperative algorithms in self-assembly. In UCNC: Unconventional Computation and Natural Computation, volume 9252 of LNCS, pages 263-276. Springer, 2015. Google Scholar
  16. Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. In SODA: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 752-771, 2014. Arxiv preprint: URL: https://arxiv.org/abs/1304.1679.
  17. Pierre-Étienne Meunier and Damien Regnault. Non-cooperatively assembling large structures. In DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Seattle, WA, USA, August 5-9, 2019, Proceedings, 2019. Google Scholar
  18. Pierre-Etienne Meunier and Damien Regnault. On the directed tile assembly systems at temperature 1. arXiv preprint, 2020. In submission with title "Directed non-cooperative tile assembly is decidable". URL: http://arxiv.org/abs/2011.09675.
  19. Pierre-Étienne Meunier, Damien Regnault, and Damien Woods. The program-size complexity of self-assembled paths. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 727-737. ACM, 2020. Arxiv preprint: https://arxiv.org/abs/2002.04012 [cs.CC]. URL: https://doi.org/10.1145/3357713.3384263.
  20. Pierre-Étienne Meunier and Damien Woods. The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. In STOC: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 328-341, Montreal, Canada, 2017. ACM. Arxiv preprint with full proofs: https://arxiv.org/abs/1702.00353v2 [cs.CC].
  21. Dionis Minev, Christopher M. Wintersinger, Anastasia Ershova, and William M. Shih. Robust nucleation control via crisscross polymerization of dna slats. bioRxiv, 2019. URL: https://doi.org/10.1101/2019.12.11.873349.
  22. Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Exact shapes and Turing universality at Temperature 1 with a single negative glue. In DNA 17: Proceedings of the Seventeenth International Conference on DNA Computing and Molecular Programming, LNCS, pages 175-189. Springer, 2011. Arxiv preprint: URL: https://arxiv.org/abs/1105.1215.
  23. Lulu Qian, Erik Winfree, and Jehoshua Bruck. Neural network computation with DNA strand displacement cascades. Nature, 475(7356):368-372, 2011. Google Scholar
  24. Paul W. K. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297-302, March 2006. URL: https://doi.org/10.1038/nature04586.
  25. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstract). In STOC: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing, pages 459-468, Portland, Oregon, 2000. ACM. URL: https://doi.org/10.1145/335305.335358.
  26. Paul W.K. Rothemund, Nick Papadakis, and Erik Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology, 2(12):2041-2053, 2004. Google Scholar
  27. David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. URL: https://doi.org/10.1137/S0097539704446712.
  28. Hao Wang. Proving theorems by pattern recognition - II. The Bell System Technical Journal, XL(1):1-41, 1961. Google Scholar
  29. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  30. Bernard Yurke, Andrew J Turberfield, Allen P Mills, Friedrich C Simmel, and Jennifer L Neumann. A DNA-fuelled molecular machine made of DNA. Nature, 406(6796):605-608, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact