Negative Interactions in Irreversible Self-assembly
- Creators
- Doty, David
- Kari, Lila
- Masson, Benoît
Abstract
This paper explores the use of negative (i.e., repulsive) interactions in the abstract Tile Assembly Model defined by Winfree. Winfree in his Ph.D. thesis postulated negative interactions to be physically plausible, and Reif, Sahu, and Yin studied them in the context of reversible attachment operations. We investigate the power of negative interactions with irreversible attachments, and we achieve two main results. Our first result is an impossibility theorem: after t steps of assembly, Ω(t) tiles will be forever bound to an assembly, unable to detach. Thus negative glue strengths do not afford unlimited power to reuse tiles. Our second result is a positive one: we construct a set of tiles that can simulate an s-space-bounded, t-time-bounded Turing machine, while ensuring that no intermediate assembly grows larger than O(s), rather than O(s⋅t) as required by the standard Turing machine simulation with tiles. In addition to the space-bounded Turing machine simulation, we show another example application of negative glues: reducing the number of tile types required to assemble "thin" (n × o(logn/loglogn)) rectangles.
Additional Information
© 2012 Springer Science+Business Media, LLC. Received: 30 January 2011; Accepted: 21 February 2012; Published online: 7 March 2012. An extended abstract of this paper appeared as [3]. This research was supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, and by the NSF Computing Innovation Fellowship grant to David Doty. The authors are grateful to Shinnosuke Seki for insightful discussions and anonymous referees for their suggestions.Additional details
- Eprint ID
- 37595
- Resolver ID
- CaltechAUTHORS:20130321-145447852
- R2824A01
- Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant
- Canada Research Chairs Program
- NSF
- Created
-
2013-03-25Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field