2026-07-22T14:20:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15948 2024-03-06T10:56:28Z ddc:004 open_access

Building Squares with Optimal State Complexity in Restricted Active Self-Assembly Alaniz, Robert M. Caballero, David Cirlos, Sonya C. Gomez, Timothy Grizzell, Elise Rodriguez, Andrew Schweller, Robert Tenorio, Armando Wylie, Tim Active Self-Assembly State Complexity Tile Automata 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 n × n 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 Θ(log^{1/4} n) states. For Single-Transition systems, where only one state may change in a transition rule, we show a bound of Θ(log^{1/3} n), and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of Θ(({log n}/{log log n})^{1/2}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert M. Alaniz and David Caballero and Sonya C. Cirlos and Timothy Gomez and Elise Grizzell and Andrew Rodriguez and Robert Schweller and Armando Tenorio and Tim Wylie 2022 Is Part Of LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2022.6 urn:nbn:de:0030-drops-159482 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode