Degree
Doctor of Philosophy
Program
Computer Science
Supervisor
Prof. Lila Kari
Abstract
DNA-based self-assembly is an autonomous process whereby a disordered system of DNA sequences forms an organized structure or pattern as a consequence of Watson-Crick complementarity of DNA sequences, without external direction.
Here, we propose self-assembly (SA) hypergraph automata as an automata-theoretic model for patterned self-assembly. We investigate the computational power of SA-hypergraph automata and show that for every recognizable picture language, there exists an SA-hypergraph automaton that accepts this language. Conversely, we prove that for any restricted SA-hypergraph automaton, there exists a Wang Tile System, a model for recognizable picture languages, that accepts the same language.
Moreover, we investigate the computational power of some variants of the Signal-passing Tile Assembly Model (STAM), as well as propose the concept of {\it Smart Tiles}, i.e., tiles with glues that can be activated or deactivated by signals, and which possess a limited amount of local computing capability. We demonstrate the potential of smart tiles to perform some robotic tasks such as replicating complex shapes.
Recommended Citation
Simjour, Amirhossein, "Self-Assembly of Tiles: Theoretical Models, the Power of Signals, and Local Computing" (2017). Electronic Thesis and Dissertation Repository. 5137.
https://ir.lib.uwo.ca/etd/5137