Search Results

Documents authored by Tenorio, Armando

Document
DOI: 10.4230/LIPIcs.SAND.2022.6
Building Squares with Optimal State Complexity in Restricted Active Self-Assembly

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

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

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 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}).
Cite as

Robert M. Alaniz, David Caballero, Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, Armando Tenorio, and Tim Wylie. Building Squares with Optimal State Complexity in Restricted Active Self-Assembly. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alaniz_et_al:LIPIcs.SAND.2022.6,
  author =	{Alaniz, Robert M. and Caballero, David and Cirlos, Sonya C. and Gomez, Timothy and Grizzell, Elise and Rodriguez, Andrew and Schweller, Robert and Tenorio, Armando and Wylie, Tim},
  title =	{{Building Squares with Optimal State Complexity in Restricted Active Self-Assembly}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.6},
  URN =		{urn:nbn:de:0030-drops-159482},
  doi =		{10.4230/LIPIcs.SAND.2022.6},
  annote =	{Keywords: Active Self-Assembly, State Complexity, Tile Automata}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact