scientific article; zbMATH DE number 7650410

DOI10.4230/LIPICS.ITCS.2020.62MaRDI QIDQ5875768zbMATH OpenFDO

Authors Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

Publication date 3 February 2023

Full work available at URL https://arxiv.org/abs/1812.03592

zbMATH Keywords

computational complexityEXPgamesmotion planningNEXPNPPSPACEundecidability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(12)

• On decidability and complexity of low-dimensional robot games
• PSPACE-completeness of reversible deterministic systems
• Traversability, reconfiguration, and reachability in the gadget framework
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Traversability, reconfiguration, and reachability in the gadget framework
• The Legend of Zelda: the complexity of mechanics
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• You can't solve these Super Mario Bros. levels: undecidable Mario games
• PSPACE-completeness of reversible deterministic systems
• Reachability in restricted chemical reaction networks
• Agent motion planning as block asynchronous cellular automata: pushing, pulling, suplexing, and more
• Characterizing universal reconfigurability of modular pivoting robots

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875768)