Reasoning about action in polynomial time
1999 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 0374-2539, Vol. 115, no 1, 1-24Article in journal (Refereed) Published
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. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
reasoning about action, logic, computational complexity, temporal logic
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-49932DOI: 10.1016/S0004-3702(99)00065-XOAI: oai:DiVA.org:liu-49932DiVA: diva2:270828