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

DOI10.1016/j.jcss.2023.103462zbMath1529.68104arXiv2211.12589MaRDI QIDQ6133652

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)

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

zbMATH Keywords

cellular automataself-assemblytile automataseeded TAsquare building

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards intrinsically universal asynchronous CA
• Computational complexity of finite asynchronous cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• 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
• New bounds on the tile complexity of thin rectangles at temperature-1
• Simulation of programmable matter systems using active tile-based self-assembly
• Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model
• Self-assembly with Geometric Tiles
• A Guided Tour of Asynchronous Cellular Automata
• 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)
• Reducing tile complexity for self-assembly through temperature programming
• P-completeness of Cellular Automaton Rule 110
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• 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
• Intrinsic universality in tile self-assembly requires cooperation
• Complexity of Self‐Assembled Shapes
• Freezing, Bounded-Change and Convergent Cellular Automata
• Signal Passing Self-Assembly Simulates Tile Automata