Reasoning about Action in Polynomial Time
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Temporal Reasoning. Pages 1447-1452.
Abstract
Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.
@inproceedings{ijcai1997p208,
title = {Reasoning about Action in Polynomial Time},
author = {Drakengren, Thomas and Bjäreland, Marcus},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1447--1452},
year = {1997},
note = {Temporal Reasoning},
url = {https://ijcai.org/proceedings/1997/208},
}
TY - CPAPER TI - Reasoning about Action in Polynomial Time AU - Drakengren, Thomas AU - Bjäreland, Marcus T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1447 EP - 1452 UR - https://ijcai.org/proceedings/1997/208 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
