Limitations of self-assembly at temperature 1
type: Item
instance of: scholarly article
title: Limitations of self-assembly at temperature 1
zbMATH Open document ID: 1234.05052
author: David Doty
author: Matthew J. Patitz
author: Scott M. Summers
published in: Theoretical Computer Science
publication date: 2011-01-10T00:00:00Z
review text: A tile system is said to be pumpable if every sufficiently long path of tiles in an assembly of this system contains a segment in which the same tile type repeats, and that furthermore, the subpath between these two occurrences can be repeated indefinitely (pumped) along the same direction as the first occurrence of the segment, without colliding with a previous portion of the path. A linear set \(X\subseteq \mathbb{Z}^{2}\) is a set of integer lattice points with the property that there are three vectors \(\vec{b}, \vec{u}\), and \(\vec{v}\), such that \(X=\{\vec{b}+n\vec{u}+m\vec{v}\mid n,m\in \mathbb{N}\}\); a set is semilinear if it is a finite union of linear sets. In this paper it is shown that if a set \(X\subseteq \mathbb{Z}^{2}\) weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assemble system satisfying the pumpability condition, then \(X\) is a semilinear set. Conversely, every semilinear set weakly self-assembles at temperature 1. This justifies the suggestion that semilinear sets are computationally very simple, based on their relationship to regular languages. Also, an application of this theorem shows that, unlike the case of temperature 2, no non-trivial discrete self-similar fractal -- such as the discrete Sierpinski triangle -- weakly self-assembles at temperature 1 in a directed, pumpable tile assembly system. Finally, some open questions are discussed.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05B45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 5834259
zbMATH Keywords: tile assembly system
zbMATH Keywords: tile self-assembly
zbMATH Keywords: general-purpose computation
zbMATH Keywords: semilinear set
zbMATH Keywords: grid graph
zbMATH Keywords: regular language
zbMATH Keywords: discrete Sierpinski triangle
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.08.023
OpenAlex ID: W2302577799
cites work: The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
cites work: Randomized Self-Assembly for Exact Shapes
cites work: Mathematical Foundations of Computer Science 2005
cites work: Q5365064
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Randomized Self-assembly for Approximate Shapes
cites work: Strict self-assembly of discrete Sierpinski triangles
cites work: Self-assembly of Decidable Sets
cites work: The program-size complexity of self-assembled squares (extended abstract)
cites work: Q5509685
DOI: 10.1016/J.TCS.2010.08.023
Recommended article: Limitations of Self-assembly at Temperature One
Recommended article: Q5365064
Recommended article: The Simulation Powers and Limitations of Higher Temperature Hierarchical Self-Assembly Systems*
Recommended article: Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly
Recommended article: Resiliency to multiple nucleation in temperature-1 self-assembly
Recommended article: Optimal self-assembly of finite shapes at temperature 1 in 3D
Recommended article: A Limit to the Power of Multiple Nucleation in Self-assembly
Recommended article: Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
description: scientific article; zbMATH DE number 5834259