LiU Electronic Press
Full-text not available in DiVA
Author:
Drakengren, Thomas (Linköping University, The Institute of Technology)
Bjäreland, Marcus (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab)
Title:
Reasoning about action in polynomial time
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, The Institute of Technology
Publication type:
Article in journal (Refereed)
Language:
English
Publisher: Elsevier
Status:
Published
In:
Artificial Intelligence(ISSN 0004-3702)(EISSN 0374-2539)
Volume:
115
Issue:
1
Pages:
1-24
Year of publ.:
1999
URI:
urn:nbn:se:liu:diva-49932
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-49932
Subject category:
Engineering and Technology
SVEP category:
TECHNOLOGY
Keywords(en) :
reasoning about action, logic, computational complexity, temporal logic
Abstract(en) :

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.

Available from:
2009-10-11
Created:
2009-10-11
Last updated:
2011-02-24
Statistics:
11 hits