PSPACE-completeness of reversible deterministic systems

DOI10.1007/978-3-031-13502-6_7MaRDI QIDQ2104136OpenAlexFDO

Authors Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson, Jayson Lynch

Publication date 9 December 2022

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 7650410 (Why is no real title available?)
• Computational complexity of motion planning of a robot through simple gadgets
• Conservative logic
• Energy-efficient algorithms
• Games, puzzles, and computation
• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets

Cited in

(5)

• scientific article; zbMATH DE number 4128407 (Why is no real title available?)
• Reversible space equals deterministic space
• J-SYSTEM RECONSTRUCT/ABILITY: A FORMALIZED STUDY
• Traversability, reconfiguration, and reachability in the gadget framework
• scientific article; zbMATH DE number 5722524 (Why is no real title available?)

This page was built for publication: PSPACE-completeness of reversible deterministic systems

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