28 citations · 139 across the 36 of their papers we have counts for
9 papers · 1 filter
Binary pattern tile set synthesis is NP-hard
Lila Kari, Steffen Kopecki, Pierre-Étienne Meunier +2
In the field of algorithmic self-assembly, a long-standing unproven conjecture has been that of the NP-hardness of binary pattern tile set synthesis (2-PATS). The -PATS problem…
Intrinsic universality in tile self-assembly requires cooperation
Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers +3
We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we…
Two Hands Are Better Than One (up to constant factors)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine +5
We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two…
Identifying Shapes Using Self-Assembly (extended abstract)
Matthew J. Patitz, Scott M. Summers
In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite…
Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)
Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller +1
We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of…
Intrinsic Universality in Self-Assembly
David Doty, Jack H. Lutz, Matthew J. Patitz +2
We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile…