2 citations · 4 across the 6 of their papers we have counts for
10 papers
Intrinsic Universality in Seeded Active Tile Self-Assembly
Tim Gomez, Elise Grizzell, Asher Haun +4
The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows…
Computing Threshold Circuits with Void Reactions in Step Chemical Reaction Networks
Rachel Anderson, Alberto Avila, Bin Fu +8
We introduce a new model of \emph{step} Chemical Reaction Networks (step CRNs), motivated by the step-wise addition of materials in standard lab procedures. Step CRNs have ordered…
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Hayashi Ani, Michael Coulombe, Erik D. Demaine +4
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-plan…
Complexity of Reconfiguration in Surface Chemical Reaction Networks
Robert M. Alaniz, Josh Brunner, Michael Coulombe +9
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent sp…
Complexity of Solo Chess with Unlimited Moves
Josh Brunner, Lily Chung, Michael Coulombe +3
We analyze Solo Chess puzzles, where the input is an board containing some standard Chess pieces of the same color, and the goal is to make a sequence of capture moves…
Building Squares with Optimal State Complexity in Restricted Active Self-Assembly
Robert M. Alaniz, David Caballero, Sonya C. Cirlos +6
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…
Reachability in Restricted Chemical Reaction Networks
Robert M. Alaniz, Bin Fu, Timothy Gomez +5
The popularity of molecular computation has given rise to several models of abstraction, one of the more recent ones being Chemical Reaction Networks (CRNs). These are equivalent t…
Unique Assembly Verification in Two-Handed Self-Assembly
David Caballero, Timothy Gomez, Robert Schweller +1
One of the most fundamental and well-studied problems in Tile Self-Assembly is the Unique Assembly Verification (UAV) problem. This algorithmic problem asks whether a given tile sy…
Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions
David Caballero, Angel A. Cantu, Timothy Gomez +3
Motivated by advances is nanoscale applications and simplistic robot agents, we look at problems based on using a global signal to move all agents when given a limited number of di…
Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
Jose Balanza-Martinez, David Caballero, Angel A. Cantu +6
We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. While pre…