Tile Reconfiguration by a Finite Automaton

The work studies how shapes can be formed and changed in programmable matter models where particles have limited memory. Here, instead of relying on memory in many particles, a single active agent has the computational power of a deterministic finite automaton. The agent can lift and place passive tiles on a triangular lattice, and it can also tell which lattice nodes are “target” versus “non-target.” The authors give an algorithm for reconfiguration into simply connected target shapes that is worst-case optimal with runtime O(mn), where m counts unoccupied target nodes and n is the total number of tiles. They also describe a method that can reconfigure a broader class of target shapes that include holes, in O(n^4) steps.