Non-deterministic Action Reversibility: Complexity Results

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00386441" target="_blank" >RIV/68407700:21230/25:00386441 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/25:00386441

Výsledek na webu

<a href="https://doi.org/10.24963/kr.2025/45" target="_blank" >https://doi.org/10.24963/kr.2025/45</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/kr.2025/45" target="_blank" >10.24963/kr.2025/45</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Non-deterministic Action Reversibility: Complexity Results

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Non-deterministic Action Reversibility: Complexity Results

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GF24-13337L" target="_blank" >GF24-13337L: Revertování efektů akcí: teorie a praxe</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

978-1-956792-08-9

ISSN

2334-1025

e-ISSN

2334-1033

Počet stran výsledku

5

Strana od-do

462-466

Název nakladatele

International Joint Conferences on Artificial Intelligence Organization

Místo vydání

—

Místo konání akce

Melbourne

Datum konání akce

11. 11. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—