publications

2023

1. Building Squares With Optimal State Complexity in Restricted Active Self-Assembly

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

   Journal of Computer and System Sciences, 2023

   Abs

   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 even with limited assembly size, 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 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 Θ(log14⁡n) states. For single-transition systems, where only one state may change in a transition rule, we show a bound of Θ(log13⁡n), and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of Θ((log⁡nlog⁡log⁡n)12). Along the way, we provide optimal bounds for the subroutines of building binary strings and building O(log⁡n)×n rectangles.

2. Complexity of Reconfiguration in Surface Chemical Reaction Networks

   Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jason Lynch, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   To appear in Proc. of the 29th International Conference on DNA Computing and Molecular Programming (DNA’23), 2023
3. Reconfiguration of Linear Surface Chemical Reaction Networks with Bounded State Change

   Robert M. Alaniz, Michael Coulombe, Erik D. Demaine, Bin Fu, Timothy Gomez, Elise Grizzell, Ryan Knobel, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   To appear in Proc. of the 35th Canadian Conference on Computational Geometry (CCCG’23), 2023
4. Problems in Algorithmic Self-Assembly and a Genetic Approach to Patterns

   Andrew Rodriguez

   Master's Thesis. University of Texas Rio Grande Valley, 2023
5. Covert Computation in the Abstract Tile-Assembly Model

   Robert M. Alaniz, David Caballero, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   In Proc. of the Symposium on Algorithmic Foundations of Dynamic Networks (SAND’23), 2023
6. Simulation of Multiple Stages in Single Bin Active Tile Self-Assembly

   Sonya C. Cirlos, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   In Proc. of the 20th International Conference on Unconventional Computation and Natural Computation (UCNC’23), 2023

2022

1. Reachability in Pikmin Cave Sublevels is PSPACE-Complete (Short Abstract)

   Andrew Rodriguez

   In The 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3’22), 2022
2. Reachability in Population Protocols is PSPACE-Complete (Short Abstract)

   Bin Fu, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   In The 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3’22), 2022
3. Building Squares with Optimal State Complexity in Restricted Active Self-Assembly

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

   In Proc. of the Symposium on Algorithmic Foundations of Dynamic Networks (SAND’22), 2022
4. Reachability in Restricted Chemical Reaction Networks

   Robert M. Alaniz, Bin Fu, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, and Tim Wylie

   2022

   arXiv