KR2025Proceedings of the 22nd International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning

Melbourne, Australia. November 11-17, 2025.

Edited by
  1. Magdalena Ortiz
  2. Renata Wassermann
  3. Torsten Schaub

ISSN: 2334-1033
ISBN: 978-1-956792-08-9

Sponsored by
Published by

Copyright © 2025 International Joint Conferences on Artificial Intelligence Organization

Non-deterministic Action Reversibility: Complexity Results

  1. Jakub Med(Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Faculty of Electrical Engineering, Czech Technical University in Prague)
  2. Michael Morak(University of Klagenfurt)
  3. Lukáš Chrpa(Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague)
  4. Wolfgang Faber(University of Klagenfurt)
PDF
BibTeX
https://doi.org/10.24963/kr.2025/45

Keywords

  1. Action Reversibility
  2. Non-deterministic Planning
  3. Computational Complexity

Abstract

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.