Traversability, reconfiguration, and reachability in the gadget framework

DOI10.1007/978-3-030-96731-4_5MaRDI QIDQ2154080zbMATH OpenOpenAlexFDO

Authors Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch

Publication date 13 July 2022

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Computational complexity of motion planning of a robot through simple gadgets
• Full tilt: universal constructors for general shapes with uniform external forces
• scientific article; zbMATH DE number 7650410 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Cited in

(3)

• Traversability, reconfiguration, and reachability in the gadget framework
• You can't solve these Super Mario Bros. levels: undecidable Mario games
• Reachability in restricted chemical reaction networks

This page was built for publication: Traversability, reconfiguration, and reachability in the gadget framework

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