Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Non-cooperative Algorithms in Self-assembly
verfasst von : Pierre-Étienne Meunier
Erschienen in: Unconventional Computation and Natural Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Imagine you are left alone in a forest with ogres and wolves, with a paper, a pen and a supply of small stones as your only weapons. How far can you go using a deterministic escape strategy, if you also want to be back in time for dinner (i.e. avoid running periodically)?
The answer to this question has been known for some time (and called the “pumping lemma”) in the simple case where the forest has exactly one self-avoiding trail: after at most \(2^n\) steps (where n is the number of bits writable on your paper) you start running periodically.
However, geometry can sometimes allow for better strategies: in this work, we show the first non-trivial positive algorithmic result (i.e. programs whose output is larger than their size), in a model of self-assembly that has been the center of puzzling open questions for almost 15 years: the planar non-cooperative variant of Winfree’s abstract Tile Assembly Model. Despite significant efforts, very little has been known on this model, until the first fully general results on its computational power, proven recently in SODA 2014.
In this model, tiles can stick to an existing assembly as soon as one of their sides matches the existing assembly. This feature contrasts with the general cooperative model, where it can be required that tiles match on several of their sides in order to bind.
Since the exact computational power of this model is still completely open, we also compare it with classical models from automata theory.