Showing 2025Show all
2 papers · 1 filter
cs.CG2025
Undecidability of Tiling with a Tromino
ULB CompGeom Group, Zachary Abel, Hugo Akitaya +6
Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling.…
cs.CC2025
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…