ML Anthology

Efficient Datalog Abduction Through Bounded Treewidth

Georg Gottlob, Reinhard Pichler, Fang Wei
AAAI 2007 pp. 1626-1631
/aaai/2007/gottlob2007aaai-efficient/

Abstract

Abductive diagnosis is an important method for identi-fying possible causes which explain a given set of obser-vations. Unfortunately, abduction suffers from the fact that most of the algorithmic problems in this area are in-tractable. We have recently obtained very promising re-sults for a strongly related problem in the database area. Specifically, the PRIMALITY problem becomes effi-ciently solvable and highly parallelizable if the under-lying functional dependencies have bounded treewidth (Gottlob, Pichler, & Wei 2006b). In the current paper, we show that these favorable results can be carried over to logic-based abduction. In fact, we even show a fur-ther generalization of these results.

PDF AAAI Semantic Scholar

Cite

Text

Gottlob et al. "Efficient Datalog Abduction Through Bounded Treewidth." AAAI Conference on Artificial Intelligence, 2007.

Markdown

[Gottlob et al. "Efficient Datalog Abduction Through Bounded Treewidth." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/gottlob2007aaai-efficient/)

BibTeX

@inproceedings{gottlob2007aaai-efficient,
  title     = {{Efficient Datalog Abduction Through Bounded Treewidth}},
  author    = {Gottlob, Georg and Pichler, Reinhard and Wei, Fang},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {1626-1631},
  url       = {https://mlanthology.org/aaai/2007/gottlob2007aaai-efficient/}
}