6 citations · 20 across the 10 of their papers we have counts for
16 papers
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…
Proving the Turing Universality of Oritatami Co-Transcriptional Folding (Full Text)
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel +1
We study the oritatami model for molecular co-transcriptional folding. In oritatami systems, the transcript (the "molecule") folds as it is synthesized (transcribed), according to…
It's a Tough Nanoworld: in Tile Assembly, Cooperation is not (strictly) more Powerful than Competition
Florent Becker, Pierre-Étienne Meunier
We present a strict separation between the class of "mismatch free" self-assembly systems and general aTAM systems. Mismatch free systems are those systems in which concurrently gr…
Noncooperative algorithms in self-assembly
Pierre-Étienne Meunier
We show the first non-trivial positive algorithmic results (i.e. programs whose output is larger than their size), in a model of self-assembly that has so far resisted many attempt…
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…
Clandestine Simulations in Cellular Automata
Pierre Guillon, Pierre-Etienne Meunier, Guillaume Theyssier
This paper studies two kinds of simulation between cellular automata: simulations based on factor and simulations based on sub-automaton. We show that these two kinds of simulation…
Communication Complexity and Intrinsic Universality in Cellular Automata
Eric Goles Chacc, Pierre-Etienne Meunier, Ivan Rapaport +1
The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains…
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…