Intrinsic Universality in Self-Assembly

DOI10.4230/LIPIcs.STACS.2010.2461zbMath1230.68071MaRDI QIDQ3113756

David Doty, Scott M. Summers, Jack H. Lutz, Damien Woods, Matthew J. Patitz

Publication date: 23 January 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_0592.html

zbMATH Keywords

self-assembly; intrinsic universality; molecular computation; biological computing

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

05B45: Combinatorial aspects of tessellation and tiling problems

Related Items

An introduction to tile-based self-assembly and a survey of recent results, The two-handed tile assembly model is not intrinsically universal, Subshifts as models for MSO logic, Binary pattern tile set synthesis is NP-hard, Optimal self-assembly of finite shapes at temperature 1 in 3D, Negative interactions in irreversible self-assembly, Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems, Parallel computation using active self-assembly, Staged self-assembly and polyomino context-free grammars, Reducing tile complexity for the self-assembly of scaled shapes through temperature programming, Unraveling simplicity in elementary cellular automata, Grids and universal computations on one-dimensional cellular automata, Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue, A Brief Tour of Theoretical Tile Self-Assembly