We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a
theoretical abstraction of many video games (introduced in 1999). The proof also extends to …

A door gadget has two states and three tunnels that can be traversed by an agent (player,
robot, etc.): the" open" and" close" tunnel sets the gadget's state to open and closed …

Consider an agent traversing a graph of “gadgets”, where each gadget has local state that
changes with each traversal by the agent according to specified rules. Prior work has …

We build a general theory for characterizing the computational complexity of motion
planning of robot (s) through a graph of" gadgets", where each gadget has its own state …

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. In this …

We analyze the computational complexity of motion planning through local “input/output”
gadgets with separate entrances and exits, and a subset of allowed traversals from …

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 …

We give both efficient algorithms and hardness results for reconfiguring between two
connected configurations of modules in the hexagonal grid. The reconfiguration moves that …

We prove PSPACE-completeness of several reversible, fully deterministic systems. At the
core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara …

Recent work has developed a theory of motion-planning gadgets, which are a useful tool for
proving hardness for a variety of problems that can be thought of in terms of an agent …