Tight Bounds for Active Self-Assembly Using an Insertion Primitive

2014/01/02 by Benjamin Hescott, Hescott, Benjamin, Caleb Malchik +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Modular Robots and Swarm Intelligence #cs.FL

paper · pdf · doi:10.48550/arxiv.1401.0359

To appear in Algorithmica. An abstract (12-page) version of this paper appeared in the proceedings of ESA 2014

openalex publication_date 2014/01/02 · arxiv created 2015/10/27 · arxiv updated 2015/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove two tight bounds on the behavior of a model of self-assembling particles introduced by Dabby and Chen (SODA 2013), called insertion systems, where monomers insert themselves into the middle of a growing linear polymer. First, we prove that the expressive power of these systems is equal to context-free grammars, answering a question posed by Dabby and Chen. Second, we prove that systems of k monomer types can deterministically construct polymers of length n = 2^Θ(k^3/2) in O(log^5/3(n)) expected time, and that this is optimal in both the number of monomer types and expected time.

Cited by

• More Tight Bounds for Active Self-Assembly Using an Insertion Primitive

Related

• More Tight Bounds for Active Self-Assembly Using an Insertion Primitive
• Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time
• Staged Self-Assembly and Polyomino Context-Free Grammars
• The program-size complexity of self-assembled paths
• Thermodynamically Favorable Computation via Tile Self-assembly