Self-assembly of decidable sets

DOI10.1007/S11047-010-9218-9MaRDI QIDQ553922zbMATH OpenOpenAlexFDO

Authors Matthew J. Patitz, Scott M. Summers

Publication date 28 July 2011

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-010-9218-9

zbMATH Keywords

DNA computingdecidabilityuniversalityspace complexitycomputabilityself-assemblytile assembly

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial aspects of tessellation and tiling problems (05B45)

Recommendations

• Self-assembly of Decidable Sets
• Self-assembling finite automata
• scientific article; zbMATH DE number 2089986
• Computability and complexity in self-assembly
• Computability and Complexity in Self-assembly
• Self-assembling pushdown automata
• Decidability results for sets with atoms
• Complexity of Compact Proofreading for Self-assembled Patterns
• Automatic decidability and combinability

Cites work

• scientific article; zbMATH DE number 1342108 (Why is no real title available?)
• A domain-specific language for programming in the tile assembly model
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• Randomized Self-Assembly for Exact Shapes
• Randomized Self-assembly for Approximate Shapes
• Reducing tile complexity for self-assembly through temperature programming
• Running time and program size for self-assembled squares
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Strict self-assembly of discrete Sierpinski triangles
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• The program-size complexity of self-assembled squares (extended abstract)
• The undecidability of the infinite ribbon problem: implications for computing by self-assembly

Cited in

(13)

• An introduction to tile-based self-assembly and a survey of recent results
• Computability and complexity in self-assembly
• Directed non-cooperative tile assembly is decidable
• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
• The undecidability of the infinite ribbon problem: implications for computing by self-assembly
• scientific article; zbMATH DE number 6905187 (Why is no real title available?)
• Fractal dimension of assemblies in the abstract tile assembly model
• The power of duples (in self-assembly): it's not so hip to be square
• Strict self-assembly of fractals using multiple hands
• Small tile sets that compute while solving mazes
• Computability and Complexity in Self-assembly
• Self-assembly of Decidable Sets
• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles

This page was built for publication: Self-assembly of decidable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553922)