Damien Woods
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Damien Woods has a total of 31 co-authors. Here are the top co-authors by number of shared publications:
- Matthew J. Patitz
Electrical Engineering and Computer Science Department, University of Arkansas, Fayetteville, USA
5 shared publications - Erik D. Demaine
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
4 shared publications - Robert T. Schweller
UNIVERSITY OF TEXAS–PAN AMERICAN
4 shared publications - Turlough Neary
University of Zürich and ETH Zürich
4 shared publications - Moya Chen
California Institute of Technology
3 shared publications - Niall Murphy
Microsoft Research
3 shared publications
Latest Publications
- 22 April 2016
- Published by Springer Nature
- p. 13-18
Active Self-Assembly and Molecular Robotics with Nubots
- 22 April 2016
- Published by Springer Nature
- p. 13-18
Active Self-Assembly and Molecular Robotics with Nubots
- Open Access
- 22 April 2016
- Published by Springer Nature
- p. 993-998
Intrinsic Universality in Self-Assembly
- 22 April 2016
- Published by Springer Nature
- p. 993-998
Open AccessIntrinsic Universality in Self-Assembly
- 28 July 2015
- Published by The Royal Society in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 373 (2046) , 20140214
Intrinsic universality and the computational power of self-assembly
Molecular self-assembly, the formation of large structures by small pieces of matter sticking together according to simple local interactions, is a ubiquitous phenomenon. A challenging engineering goal is to design a few molecules so that large numbers of them can self-assemble into desired complicated target objects. Indeed, we would like to understand the ultimate capabilities and limitations of this bottom-up fabrication process. We look to theoretical models of algorithmic self-assembly, where small square tiles stick together according to simple local rules in order to carry out a crystal growth process. In this survey, we focus on the use of simulation between such models to classify and separate their computational and expressive powers. Roughly speaking, one model simulates another if they grow the same structures, via the same dynamical growth processes. Our journey begins with the result that there is a single intrinsically universal tile set that, with appropriate initialization and spatial scaling, simulates any instance of Winfree's abstract Tile Assembly Model. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system in a very direct way. From there we find that there is no such tile set in the more restrictive non-cooperative model, proving it weaker than the full Tile Assembly Model. In the two-handed model, where large structures can bind together in one step, we encounter an infinite set of infinite hierarchies of strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that simulates any tile assembly system. We find another tile that aperiodically tiles the plane (but with small gaps). These and other recent results show that simulation is giving rise to a kind of computational complexity theory for self-assembly. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.
- 28 July 2015
- Published by The Royal Society in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 373 (2046) , 20140214
Intrinsic universality and the computational power of self-assembly
Molecular self-assembly, the formation of large structures by small pieces of matter sticking together according to simple local interactions, is a ubiquitous phenomenon. A challenging engineering goal is to design a few molecules so that large numbers of them can self-assemble into desired complicated target objects. Indeed, we would like to understand the ultimate capabilities and limitations of this bottom-up fabrication process. We look to theoretical models of algorithmic self-assembly, where small square tiles stick together according to simple local rules in order to carry out a crystal growth process. In this survey, we focus on the use of simulation between such models to classify and separate their computational and expressive powers. Roughly speaking, one model simulates another if they grow the same structures, via the same dynamical growth processes. Our journey begins with the result that there is a single intrinsically universal tile set that, with appropriate initialization and spatial scaling, simulates any instance of Winfree's abstract Tile Assembly Model. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system in a very direct way. From there we find that there is no such tile set in the more restrictive non-cooperative model, proving it weaker than the full Tile Assembly Model. In the two-handed model, where large structures can bind together in one step, we encounter an infinite set of infinite hierarchies of strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that simulates any tile assembly system. We find another tile that aperiodically tiles the plane (but with small gaps). These and other recent results show that simulation is giving rise to a kind of computational complexity theory for self-assembly. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.
- 10 June 2015
- Published by Springer Nature
- p. 1-7
Active Self-Assembly and Molecular Robotics with Nubots
- 10 June 2015
- Published by Springer Nature
- p. 1-7
Active Self-Assembly and Molecular Robotics with Nubots
- Open Access
- 4 June 2015
- Published by Springer Nature
- p. 11-16
Tag Systems and the Complexity of Simple Programs
- 4 June 2015
- Published by Springer Nature
- p. 11-16
Open AccessTag Systems and the Complexity of Simple Programs
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 251-258
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines
In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 251-258
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines
In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.
- 19 February 2015
- Published by Springer Nature in Algorithmica
- Vol. 74 (2) , 812-850
The Two-Handed Tile Assembly Model is not Intrinsically Universal
- 19 February 2015
- Published by Springer Nature in Algorithmica
- Vol. 74 (2) , 812-850
The Two-Handed Tile Assembly Model is not Intrinsically Universal
- 1 January 2015
- Published by Springer Nature
- p. 117-126
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
- 1 January 2015
- Published by Springer Nature
- p. 117-126
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
- Open Access
Uniformity is weaker than semi-uniformity for some membrane systems
We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.
Open AccessUniformity is weaker than semi-uniformity for some membrane systems
We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.