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

DOI10.1016/J.JCSS.2023.103462zbMATH Open1529.68104arXiv2211.12589MaRDI QIDQ6133652FDOQ6133652

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

Publication date: 21 August 2023

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

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)$.

Full work available at URL: https://arxiv.org/abs/2211.12589

zbMATH Keywords

cellular automataself-assemblytile automataseeded TAsquare building

Mathematics Subject Classification ID

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

Cites Work

• Self-assembly with Geometric Tiles
• Title not available (Why is that?)
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
• The program-size complexity of self-assembled squares (extended abstract)
• Running time and program size for self-assembled squares
• Turing Universality of Step-Wise and Stage Assembly at Temperature 1
• Complexities for Generalized Models of Self-Assembly
• Title not available (Why is that?)
• Intrinsic universality in tile self-assembly requires cooperation
• Complexity of Self‐Assembled Shapes
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Communication complexity and intrinsic universality in cellular automata
• Towards intrinsically universal asynchronous CA
• Computational complexity of finite asynchronous cellular automata
• A Guided Tour of Asynchronous Cellular Automata
• P-completeness of Cellular Automaton Rule 110
• Reducing tile complexity for self-assembly through temperature programming
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• Freezing simulates non-freezing tile automata
• The power of duples (in self-assembly): it's not so hip to be square
• Optimal staged self-assembly of general shapes
• Title not available (Why is that?)
• Simulation of programmable matter systems using active tile-based self-assembly
• Signal Passing Self-Assembly Simulates Tile Automata
• New bounds on the tile complexity of thin rectangles at temperature-1
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• Freezing, Bounded-Change and Convergent Cellular Automata
• Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model

Cited In (2)

• Non-determinism reduces construction time in active self-assembly using an insertion primitive
• Active Self-Assembly of Simple Units 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)