Document Open Access Logo

Building Squares with Optimal State Complexity in Restricted Active Self-Assembly

Authors Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, Armando Tenorio, Tim Wylie

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.6.pdf
  • Filesize: 0.93 MB
  • 18 pages

Document Identifiers

Author Details

Robert M. Alaniz
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
David Caballero
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Sonya C. Cirlos
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Timothy Gomez
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Elise Grizzell
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Andrew Rodriguez
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Robert Schweller
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Armando Tenorio
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Tim Wylie
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA

Funding

This research was supported in part by National Science Foundation Grant CCF-1817602.

Acknowledgements

We would like to thank the reviewers for their comments, specifically for pointing us toward relevant Cellular Automata Literature.

Cite AsGet BibTex

Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, Armando Tenorio, and Tim Wylie. Building Squares with Optimal State Complexity in Restricted Active Self-Assembly. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.6

Abstract

Tile Automata is a recently defined model of self-assembly that borrows many concepts from cellular automata to create active self-assembling systems where changes may be occurring within an assembly without requiring attachment. This model has been shown to be powerful, but many fundamental questions have yet to be explored. Here, we study the state complexity of assembling n × n squares in seeded Tile Automata systems where growth starts from a seed and tiles may attach one at a time, similar to the abstract Tile Assembly Model. We provide optimal bounds for three classes of seeded Tile Automata systems (all without detachment), which vary in the amount of complexity allowed in the transition rules. We show that, in general, seeded Tile Automata systems require Θ(log^{1/4} n) states. For Single-Transition systems, where only one state may change in a transition rule, we show a bound of Θ(log^{1/3} n), and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of Θ(({log n}/{log log n})^{1/2}).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Applied computing → Computational biology
  • Theory of computation → Self-organization
Keywords
  • Active Self-Assembly
  • State Complexity
  • Tile Automata

Metrics

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

Supplementary Materials

References

  1. Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang. Running time and program size for self-assembled squares. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 740-748, 2001. Google Scholar
  2. Gagan Aggarwal, Qi Cheng, Michael H Goldwasser, Ming-Yang Kao, Pablo Moisset De Espanes, and Robert T Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34(6):1493-1515, 2005. Google Scholar
  3. John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, and Andréa W. Richa. Simulation of programmable matter systems using active tile-based self-assembly. In Chris Thachuk and Yan Liu, editors, DNA Computing and Molecular Programming, pages 140-158, Cham, 2019. Springer International Publishing. Google Scholar
  4. Bahar Behsaz, Ján Maňuch, and Ladislav Stacho. Turing universality of step-wise and stage assembly at temperature 1. In Darko Stefanovic and Andrew Turberfield, editors, DNA Computing and Molecular Programming, pages 1-11, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  5. David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Verification and Computation in Restricted Tile Automata. In Cody Geary and Matthew J. Patitz, editors, 26th International Conference on DNA Computing and Molecular Programming (DNA 26), volume 174 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DNA.2020.10.
  6. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, and Andrew Winslow. Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 172-184. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  7. Angel A Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Signal passing self-assembly simulates tile automata. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  8. Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie. Freezing simulates non-freezing tile automata. In David Doty and Hendrik Dietz, editors, DNA Computing and Molecular Programming, pages 155-172, Cham, 2018. Springer International Publishing. Google Scholar
  9. Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, and Tim Wylie. Optimal staged self-assembly of general shapes. Algorithmica, 80(4):1383-1409, 2018. Google Scholar
  10. Gourab Chatterjee, Neil Dalchau, Richard A. Muscat, Andrew Phillips, and Georg Seelig. A spatially localized architecture for fast and modular DNA computing. Nature Nanotechnology, July 2017. URL: https://www.microsoft.com/en-us/research/publication/spatially-localized-architecture-fast-modular-dna-computing/.
  11. Matthew Cook, Yunhui Fu, and Robert Schweller. Temperature 1 self-assembly: Deterministic assembly in 3d and probabilistic assembly in 2d. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 570-589. SIAM, 2011. Google Scholar
  12. Erik D Demaine, Martin L Demaine, Sándor P Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T Schweller, and Diane L Souvaine. Staged self-assembly: nanomanufacture of arbitrary shapes with o (1) glues. Natural Computing, 7(3):347-370, 2008. Google Scholar
  13. Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Giancarlo Mauri, and Antonio E Porreca. Computational complexity of finite asynchronous cellular automata. Theoretical Computer Science, 664:131-143, 2017. Google Scholar
  14. 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 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 302-310. IEEE, 2012. Google Scholar
  15. Nazim Fates. A guided tour of asynchronous cellular automata. In International Workshop on Cellular Automata and Discrete Complex Systems, pages 15-30. Springer, 2013. Google Scholar
  16. Bin Fu, Matthew J Patitz, Robert T Schweller, and Robert Sheline. Self-assembly with geometric tiles. In International Colloquium on Automata, Languages, and Programming, pages 714-725. Springer, 2012. Google Scholar
  17. David Furcy, Scott M. Summers, and Logan Withers. Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D. In Matthew R. Lakin and Petr Šulc, editors, 27th International Conference on DNA Computing and Molecular Programming (DNA 27), volume 205 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DNA.27.4.
  18. Oscar Gilbert, Jacob Hendricks, Matthew J Patitz, and Trent A Rogers. Computing in continuous space with self-assembling polygonal tiles. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 937-956. SIAM, 2016. Google Scholar
  19. Eric Goles, P-E Meunier, Ivan Rapaport, and Guillaume Theyssier. Communication complexity and intrinsic universality in cellular automata. Theoretical Computer Science, 412(1-2):2-21, 2011. Google Scholar
  20. Eric Goles, Nicolas Ollinger, and Guillaume Theyssier. Introducing freezing cellular automata. In Cellular Automata and Discrete Complex Systems, 21st International Workshop (AUTOMATA 2015), volume 24, pages 65-73, 2015. Google Scholar
  21. Leopold N Green, Hari KK Subramanian, Vahid Mardanlou, Jongmin Kim, Rizal F Hariadi, and Elisa Franco. Autonomous dynamic control of DNA nanostructure self-assembly. Nature chemistry, 11(6):510-520, 2019. Google Scholar
  22. Daniel Hader and Matthew J Patitz. Geometric tiles and powers and limitations of geometric hindrance in self-assembly. Natural Computing, 20(2):243-258, 2021. Google Scholar
  23. Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, and Scott M. Summers. The power of duples (in self-assembly): It’s not so hip to be square. Theoretical Computer Science, 743:148-166, 2018. URL: https://doi.org/10.1016/j.tcs.2015.12.008.
  24. Ming-Yang Kao and Robert Schweller. Reducing tile complexity for self-assembly through temperature programming. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 571-580, USA, 2006. Society for Industrial and Applied Mathematics. Google Scholar
  25. Pierre-Etienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 752-771, 2014. URL: https://doi.org/10.1137/1.9781611973402.56.
  26. Pierre-Étienne Meunier and Damien Regnault. Directed Non-Cooperative Tile Assembly Is Decidable. In Matthew R. Lakin and Petr Šulc, editors, 27th International Conference on DNA Computing and Molecular Programming (DNA 27), volume 205 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DNA.27.6.
  27. Pierre-Étienne Meunier and Damien Woods. The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 328-341, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055446.
  28. Turlough Neary and Damien Woods. P-completeness of cellular automaton rule 110. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, pages 132-143, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  29. Nicolas Ollinger and Guillaume Theyssier. Freezing, bounded-change and convergent cellular automata. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.06751.
  30. Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Exact shapes and Turing universality at temperature 1 with a single negative glue. In Proceedings of the 17th International Conference on DNA Computing and Molecular Programming, DNA'11, pages 175-189, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
  31. Paul WK Rothemund and Erik Winfree. The program-size complexity of self-assembled squares. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 459-468, 2000. Google Scholar
  32. Nicholas Schiefer and Erik Winfree. Time complexity of computation and construction in the chemical reaction network-controlled tile assembly model. In Yannick Rondelez and Damien Woods, editors, DNA Computing and Molecular Programming, pages 165-182, Cham, 2016. Springer International Publishing. Google Scholar
  33. David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. Google Scholar
  34. Anupama J. Thubagere, Wei Li, Robert F. Johnson, Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, and Lulu Qian. A cargo-sorting DNA robot. Science, 357(6356):eaan6558, 2017. URL: https://doi.org/10.1126/science.aan6558.
  35. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  36. Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin. Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 353-354, 2013. Google Scholar
  37. Thomas Worsch. Towards intrinsically universal asynchronous ca. Natural Computing, 12(4):539-550, 2013. 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 Imprint Privacy Contact