Journal article icon

Journal article

Bounded treewidth as a key to tractability of knowledge representation and reasoning

Abstract:

Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved f...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1016/j.artint.2009.10.003

Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical,Physical & Life Sciences Division - Computer Science,Department of
Role:
Author
Publisher:
Elsevier B.V. Publisher's website
Journal:
Artificial Intelligence Journal website
Volume:
174
Issue:
1
Pages:
105–132
Publication date:
2010-01-05
DOI:
ISSN:
0004-3702
URN:
uuid:b1a52418-89ab-42e8-9145-94a53bf92eb2
Local pid:
ora:8098

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP