{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:27:31Z","timestamp":1762504051234,"version":"build-2065373602"},"reference-count":10,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara and a framework for motion planning through gadgets), showing that any system that can implement three basic gadgets is PSPACE-complete. We then apply this framework to four different systems, showing its versatility. First, we prove that Deterministic Constraint Logic is PSPACE-complete, fixing an error in a previous argument from 2008. Second, we give a new PSPACE-hardness proof for the reversible \u2018billiard ball\u2019 model of Fredkin and Toffoli from 40 years ago, newly establishing hardness when only two balls move at once. Third, we prove PSPACE-completeness of zero-player motion planning with any reversible deterministic interacting k-tunnel gadget and a \u2018rotate clockwise\u2019 gadget (a zero-player analog of branching hallways). Fourth, we give simpler proofs that zero-player motion planning is PSPACE-complete with just a single gadget, the 3-spinner. These results should in turn make it even easier to prove PSPACE-hardness of other reversible deterministic systems.<\/jats:p>","DOI":"10.1142\/s0129054123470032","type":"journal-article","created":{"date-parts":[[2023,7,30]],"date-time":"2023-07-30T22:20:47Z","timestamp":1690755647000},"page":"1041-1062","source":"Crossref","is-referenced-by-count":0,"title":["PSPACE-Completeness of Reversible Deterministic Systems"],"prefix":"10.1142","volume":"36","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA"}]},{"given":"Robert A.","family":"Hearn","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA"}]},{"given":"Dylan","family":"Hendrickson","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA"}]},{"given":"Jayson","family":"Lynch","sequence":"additional","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA"}]}],"member":"219","published-online":{"date-parts":[[2023,7,29]]},"reference":[{"key":"S0129054123470032BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-96731-4_16"},{"key":"S0129054123470032BIB002","first-page":"18:1","volume-title":"Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018)","author":"Demaine E. D.","year":"2018"},{"key":"S0129054123470032BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.35"},{"key":"S0129054123470032BIB004","first-page":"62:1","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)","author":"Demaine E. D.","year":"2020"},{"key":"S0129054123470032BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840756"},{"key":"S0129054123470032BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/ICRC.2017.8123659"},{"key":"S0129054123470032BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"key":"S0129054123470032BIB009","doi-asserted-by":"publisher","DOI":"10.1201\/b10581"},{"key":"S0129054123470032BIB011","doi-asserted-by":"publisher","DOI":"10.1038\/s41563-019-0304-9"},{"key":"S0129054123470032BIB012","doi-asserted-by":"publisher","DOI":"10.3390\/a4010001"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123470032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:17:03Z","timestamp":1762503423000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123470032"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,29]]},"references-count":10,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1142\/S0129054123470032"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123470032","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,7,29]]}}}