Expressive Reasoning about Action in Nondeterministic Polynomial Time
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 166-170.
Abstract
Th e rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of actions, and actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.
@inproceedings{ijcai1999p25,
title = {Expressive Reasoning about Action in Nondeterministic Polynomial Time},
author = {Drakengren, Thomas and Bjäreland, Marcus},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {166--170},
year = {1999},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1999/25},
}
TY - CPAPER TI - Expressive Reasoning about Action in Nondeterministic Polynomial Time AU - Drakengren, Thomas AU - Bjäreland, Marcus T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 166 EP - 170 UR - https://ijcai.org/proceedings/1999/25 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
