Bounded treewidth as a key to tractability of knowledge representation and reasoning
<p>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 t...
| Main Authors: | , , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
Elsevier
2010
|
| Assuntos: |
| _version_ | 1826291691618828288 |
|---|---|
| author | Gottlob, G Pichler, R Wei, F |
| author_facet | Gottlob, G Pichler, R Wei, F |
| author_sort | Gottlob, G |
| collection | OXFORD |
| description | <p>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 formulae or programs is bounded by some constant.</p> <p>Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.</p> |
| first_indexed | 2024-03-07T03:03:13Z |
| format | Journal article |
| id | oxford-uuid:b1a52418-89ab-42e8-9145-94a53bf92eb2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:03:13Z |
| publishDate | 2010 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:b1a52418-89ab-42e8-9145-94a53bf92eb22022-03-27T04:05:42ZBounded treewidth as a key to tractability of knowledge representation and reasoningJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b1a52418-89ab-42e8-9145-94a53bf92eb2Applications and algorithmsEnglishOxford University Research Archive - ValetElsevier2010Gottlob, GPichler, RWei, F<p>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 formulae or programs is bounded by some constant.</p> <p>Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.</p> |
| spellingShingle | Applications and algorithms Gottlob, G Pichler, R Wei, F Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title | Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title_full | Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title_fullStr | Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title_full_unstemmed | Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title_short | Bounded treewidth as a key to tractability of knowledge representation and reasoning |
| title_sort | bounded treewidth as a key to tractability of knowledge representation and reasoning |
| topic | Applications and algorithms |
| work_keys_str_mv | AT gottlobg boundedtreewidthasakeytotractabilityofknowledgerepresentationandreasoning AT pichlerr boundedtreewidthasakeytotractabilityofknowledgerepresentationandreasoning AT weif boundedtreewidthasakeytotractabilityofknowledgerepresentationandreasoning |