LIPIcs.ISAAC.2020.53.pdf
- Filesize: 1.04 MB
- 17 pages
Document
Signal Passing Self-Assembly Simulates Tile Automata
Authors
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
Cite As Get BibTex
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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.53
Abstract
The natural process of self-assembly has been studied through various abstract models due to the abundant applications that benefit from self-assembly. Many of these different models emerged in an effort to capture and understand the fundamental properties of different physical systems and the mechanisms by which assembly may occur. A newly proposed model, known as Tile Automata, offers an abstract toolkit to analyze and compare the algorithmic properties of different self-assembly systems. In this paper, we show that for every Tile Automata system, there exists a Signal-passing Tile Assembly system that can simulate it. Finally, we connect our result with a recent discovery showing that Tile Automata can simulate Amoebot programmable matter systems, thus showing that the Signal-passing Tile Assembly can simulate any Amoebot system.
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
- Applied computing → Computational biology
Keywords
- self-assembly
- signal-passing tile assembly model
- tile automata
- cellular automata
- simulation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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.
-
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.
-
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.
-
Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. Computing by Programmable Particles, pages 615-681. Springer International Publishing, Cham, 2019.
-
Tyler Fochtman, Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, and Trent A. Rogers. Signal transmission across tile assemblies: 3d static tiles simulate active self-assembly by 2d signal-passing tiles. Natural Computing, 14(2):251-264, June 2015.
-
Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles. In Cristian S. Calude and Michael J. Dinneen, editors, Unconventional Computation and Natural Computation, pages 202-214, Cham, 2015. Springer International Publishing.
-
Jarkko Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334(1):3-33, 2005.
-
Alexandra Keenan, Robert Schweller, and Xingsi Zhong. Exponential replication of patterns in the signal tile assembly model. Natural Computing, 14(2):265-278, June 2015.
-
Jennifer E. Padilla, Wenyan Liu, and Nadrian C. Seeman. Hierarchical self assembly of patterns from the robinson tilings: Dna tile design in an enhanced tile assembly model. Natural Computing, 11(2):323-338, June 2012.
-
Jennifer E. Padilla, Matthew J. Patitz, Robert T. Schweller, Nadrian C. Seeman, Scott M. Summers, and Xingsi Zhong. Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. International Journal of Foundations of Computer Science, 25(04):459-488, 2014.
-
Jennifer E. Padilla, Ruojie Sha, Martin Kristiansen, Junghuei Chen, Natasha Jonoska, and Nadrian C. Seeman. A signal-passing dna-strand-exchange mechanism for active self-assembly of dna nanostructures. Angewandte Chemie International Edition, 54(20):5939-5942, 2015.