Reasoning About Action in Polynomial Time
Abstract
Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this article 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.
Cite
Text
Drakengren and Bjäreland. "Reasoning About Action in Polynomial Time." International Joint Conference on Artificial Intelligence, 1997. doi:10.1016/S0004-3702(99)00065-XMarkdown
[Drakengren and Bjäreland. "Reasoning About Action in Polynomial Time." International Joint Conference on Artificial Intelligence, 1997.](https://mlanthology.org/ijcai/1997/drakengren1997ijcai-reasoning/) doi:10.1016/S0004-3702(99)00065-XBibTeX
@inproceedings{drakengren1997ijcai-reasoning,
title = {{Reasoning About Action in Polynomial Time}},
author = {Drakengren, Thomas and Bjäreland, Marcus},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1997},
pages = {1447-1453},
doi = {10.1016/S0004-3702(99)00065-X},
url = {https://mlanthology.org/ijcai/1997/drakengren1997ijcai-reasoning/}
}