Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
From MaRDI portal
Abstract: We describe a computational model for studying the complexity of self-assembled structures with active molecular components. Our model captures notions of growth and movement ubiquitous in biological systems. The model is inspired by biology's fantastic ability to assemble biomolecules that form systems with complicated structure and dynamics, from molecular motors that walk on rigid tracks and proteins that dynamically alter the structure of the cell during mitosis, to embryonic development where large-scale complicated organisms efficiently grow from a single cell. Using this active self-assembly model, we show how to efficiently self-assemble shapes and patterns from simple monomers. For example, we show how to grow a line of monomers in time and number of monomer states that is merely logarithmic in the length of the line. Our main results show how to grow arbitrary connected two-dimensional geometric shapes and patterns in expected time that is polylogarithmic in the size of the shape, plus roughly the time required to run a Turing machine deciding whether or not a given pixel is in the shape. We do this while keeping the number of monomer types logarithmic in shape size, plus those monomers required by the Kolmogorov complexity of the shape or pattern. This work thus highlights the efficiency advantages of active self-assembly over passive self-assembly and motivates experimental effort to construct general-purpose active molecular self-assembly systems.
Recommendations
Cites work
- A model of interactive teaching
- A theory of goal-oriented communication
- A theory of the learnable
- Algorithmic Learning Theory
- Derandomizing polynomial identity tests means proving circuit lower bounds
- scientific article; zbMATH DE number 3154781 (Why is no real title available?)
- scientific article; zbMATH DE number 67625 (Why is no real title available?)
- scientific article; zbMATH DE number 67631 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Learning from different teachers
- Measuring teachability using variants of the teaching dimension
- Models of cooperative teaching and learning
- Occam's razor
- On specifying Boolean functions by labelled examples
- On the complexity of teaching
- On the limits of efficient teachability
- On the power of inductive inference from good examples
- Pseudorandom generators for space-bounded computation
- Recent Developments in Algorithmic Teaching
- Teachability in computational learning
- Teaching a smarter learner.
- Teaching Randomized Learners
Cited in
(43)- Terminating distributed construction of shapes and patterns in a fair solution of automata
- A minimal requirement for self-assembly of lines in polylogarithmic time
- On the transformation capability of feasible mechanisms for programmable matter
- Non-determinism reduces construction time in active self-assembly using an insertion primitive
- Parallel computation using active self-assembly
- Shape formation by programmable particles
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- CADbots: algorithmic aspects of manipulating programmable matter with finite automata
- An introduction to tile-based self-assembly and a survey of recent results
- Fast algorithmic self-assembly of simple shapes using random agitation
- Leader election and shape formation with self-organizing programmable matter
- Network Constructors: A Model for Programmable Matter
- scientific article; zbMATH DE number 2152822 (Why is no real title available?)
- Connectivity preserving network transformers
- Shape recognition by a finite automaton robot
- Improved Leader Election for Self-organizing Programmable Matter
- Parallel Computation Using Active Self-assembly
- Iterative self-assembly with dynamic strength transformation and temperature control
- Connectivity preserving network transformers
- Active Self-Assembly of Simple Units Using an Insertion Primitive
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- Connected reconfiguration of lattice-based cellular structures by finite-memory robots
- Distributed transformations of Hamiltonian shapes based on line moves
- Distributed transformations of Hamiltonian shapes based on line moves
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- A minimal requirement for self-assembly of lines in polylogarithmic time
- Turning machines
- The canonical amoebot model: algorithms and concurrency control
- On geometric shape construction via growth operations
- Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes
- The complexity of growing a graph
- Building squares with optimal state complexity in restricted active self-assembly
- On geometric shape construction via growth operations
- Forming tile shapes with simple robots
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- The complexity of growing a graph
- Deterministic self-stabilising leader election for programmable matter with constant memory
- Efficient shape formation by 3D hybrid programmable matter: an algorithm for low diameter intermediate structures
- All for one and one for all: an O(1)-musketeers generic transformation for rotating robots
- On the exponential growth of geometric shapes
- Transformation of modular robots by rotation: 3 + 1 musketeers for all orthogonally convex shapes
- Deterministic leader election for stationary programmable matter with common direction
- Collision detection for modular robots -- it is easy to cause collisions and hard to avoid them
This page was built for publication: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986885)
