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 analyze the computational complexity of motion planning through local “input/output”
gadgets with separate entrances and exits, and a subset of allowed traversals from …

We analyze some of the many game mechanics available to Link in the classic Legend of
Zelda series of video games. In each case, we prove that the generalized game with that …

In this paper, we explore how agent reachability problems from motion planning, games,
and puzzles can be generalized and analyzed from the perspective of block asynchronous …

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 …

Using the notion of visibility representations, our paper establishes a new property of
instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete …

We prove RE-completeness (and thus undecidability) of several 2D games in the Super
Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U …

We prove RE-completeness (and thus undecidability) of several 2D games in the Super
Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U …

We consider the computational complexity of constant-area levels of games which allow an
unlimited number of objects in a fixed region. We discuss how to prove that such games are …

We analyze some of the many game mechanics available to Link in the classic Legend of
Zelda series of video games. In each case, we prove that the generalized game with that …