PSPACE-completeness of reversible deterministic systems

DOI10.1007/978-3-031-13502-6_7OpenAlexW4290017147MaRDI QIDQ2104136FDOQ2104136

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

• Conservative logic
• Games, puzzles, and computation
• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• Title not available (Why is that?)
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Energy-efficient algorithms
• Computational complexity of motion planning of a robot through simple gadgets

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• J-SYSTEM RECONSTRUCT/ABILITY: A FORMALIZED STUDY
• Reversible space equals deterministic space
• Traversability, reconfiguration, and reachability in the gadget framework

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)