6 citations · 20 across the 10 of their papers we have counts for
11 papers · 1 filter
On the directed tile assembly systems at temperature 1
Pierre-Étienne Meunier, Damien Regnault
We show here that a model called directed self-assembly at temperature 1 is unable to do complex computations like the ones of a Turing machine. Since this model can be seen as a g…
The program-size complexity of self-assembled paths
Pierre-Étienne Meunier, Damien Regnault, Damien Woods
We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theo…
Non-cooperatively assembling large structures: a 2D pumping lemma cannot be as powerful as its 1D counterpart
Pierre-Etienne Meunier, Damien Regnault
We show the first asymptotically efficient constructions in the so-called "noncooperative planar tile assembly" model. Algorithmic self-assembly is the study of the local, distribu…
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
Pierre-Étienne Meunier, Damien Woods
The field of algorithmic self-assembly is concerned with the computational and expressive power of nanoscale self-assembling molecular systems. In the well-studied cooperative, or…
A pumping lemma for non-cooperative self-assembly
Pierre-Étienne Meunier, Damien Regnault
We prove a result which strongly hints at the computational weakness of a model of tile assembly that has so far resisted many attempts of formal analysis or positive constructions…
Unraveling simplicity in elementary cellular automata
Pierre-Étienne Meunier
We show that a large number of elementary cellular automata are computationally simple. This work is the first systematic classification of elementary cellular automata based on a…
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…
The self-assembly of paths and squares at temperature 1
Pierre-Étienne Meunier
We prove that the number of tile types required to build squares of size n x n, in Winfree's abstract Tile Assembly Model, when restricted to using only non-cooperative tile bindin…
A pumping lemma for non-cooperative self-assembly
Pierre-Étienne Meunier, Damien Regnault
We prove the computational weakness of a model of tile assembly that has so far resisted many attempts of formal analysis or positive constructions. Specifically, we prove that, in…
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…
Communications in cellular automata
Eric Goles, Pierre-Etienne Meunier, Ivan Rapaport +1
The goal of this paper is to show why the framework of communication complexity seems suitable for the study of cellular automata. Researchers have tackled different algorithmic pr…