Building squares with optimal state complexity in restricted active self-assembly

DOI10.1016/J.JCSS.2023.103462MaRDI QIDQ6133652zbMATH OpenFDO

Authors Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert T. Schweller, Armando Tenorio, Tim Wylie

Publication date 21 August 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.12589, https://scholarworks.utrgv.edu/cs_fac/100

zbMATH Keywords

cellular automataself-assemblytile automataseeded TAsquare building

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Cellular automata (computational aspects) (68Q80)

Abstract: Tile Automata is a recently defined model of self-assembly that borrows many concepts from cellular automata to create active self-assembling systems where changes may be occurring within an assembly without requiring attachment. This model has been shown to be powerful, but many fundamental questions have yet to be explored. Here, we study the state complexity of assembling $nimesn$ squares in seeded Tile Automata systems where growth starts from a seed and tiles may attach one at a time, similar to the abstract Tile Assembly Model. We provide optimal bounds for three classes of seeded Tile Automata systems (all without detachment), which vary in the amount of complexity allowed in the transition rules. We show that, in general, seeded Tile Automata systems require $Theta(lo{g}^{frac14}n)$ states. For single-transition systems, where only one state may change in a transition rule, we show a bound of $Theta(lo{g}^{frac13}n)$, and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of $Theta((fraclognloglogn{)}^{f}rac12)$.

Recommendations

• Verification and computation in restricted tile automata
• The program-size complexity of self-assembled squares (extended abstract)
• Complexities for generalized models of self-assembly
• Complexities for Generalized Models of Self-Assembly
• Hypergraph automata: a theoretical model for patterned self-assembly

Cites work

• A guided tour of asynchronous cellular automata
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Communication complexity and intrinsic universality in cellular automata
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• Computational complexity of finite asynchronous cellular automata
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• Exact shapes and Turing universality at temperature 1 with a single negative glue
• Freezing simulates non-freezing tile automata
• Freezing, bounded-change and convergent cellular automata
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
• Intrinsic universality in tile self-assembly requires cooperation
• New bounds on the tile complexity of thin rectangles at temperature-1
• Optimal staged self-assembly of general shapes
• P-completeness of Cellular Automaton Rule 110
• Reducing tile complexity for self-assembly through temperature programming
• Running time and program size for self-assembled squares
• Self-assembly with geometric tiles
• Signal Passing Self-Assembly Simulates Tile Automata
• Simulation of programmable matter systems using active tile-based self-assembly
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• The power of duples (in self-assembly): it's not so hip to be square
• The program-size complexity of self-assembled squares (extended abstract)
• Time complexity of computation and construction in the chemical reaction network-controlled tile assembly model
• Towards intrinsically universal asynchronous CA
• Turing universality of step-wise and stage assembly at temperature 1
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM

Cited in

(3)

• Verification and computation in restricted tile automata
• Active Self-Assembly of Simple Units Using an Insertion Primitive
• Non-determinism reduces construction time in active self-assembly using an insertion primitive

This page was built for publication: Building squares with optimal state complexity in restricted active self-assembly

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