{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T07:00:53Z","timestamp":1762326053335,"version":"build-2065373602"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>With the recent interest in the reversibility of action effects, i.e., whether the effects of the action can be undone by applying other actions, the question arose how hard it is to reverse an action in a non-deterministic domain. With the use of phi-reversibility, the paper investigates the computational complexity of weak and strong non-deterministic action reversibility in fully observable non-deterministic domains, showing PSPACE-completeness for all weak variants in question and EXP-hardness and EXP, or NEXP memberships for strong variants.<\/jats:p>","DOI":"10.24963\/kr.2025\/45","type":"proceedings-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:44Z","timestamp":1762323044000},"page":"462-466","source":"Crossref","is-referenced-by-count":0,"title":["Non-deterministic Action Reversibility: Complexity Results"],"prefix":"10.24963","author":[{"given":"Jakub","family":"Med","sequence":"first","affiliation":[{"name":"Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague"},{"name":"Faculty of Electrical Engineering, Czech Technical University in Prague"}]},{"given":"Michael","family":"Morak","sequence":"additional","affiliation":[{"name":"University of Klagenfurt"}]},{"given":"Luk\u00e1\u0161","family":"Chrpa","sequence":"additional","affiliation":[{"name":"Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague"}]},{"given":"Wolfgang","family":"Faber","sequence":"additional","affiliation":[{"name":"University of Klagenfurt"}]}],"member":"10584","event":{"name":"22nd International Conference on Principles of Knowledge Representation and Reasoning {KR-2025}","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"KR-2025","number":"22","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2025,11,11]]},"end":{"date-parts":[[2025,11,17]]}},"container-title":["Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:11:11Z","timestamp":1762323071000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2025\/45"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2025\/45","relation":{},"subject":[],"published":{"date-parts":[[2025,11]]}}}