A Tractable Class of Abduction Problems

Eshghi, Kave

A Tractable Class of Abduction Problems

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 3-7.

Abstract

The problem of fmding a set of assumptions which explain a given proposition is in general NP-hard, even when the background theory is an acyclic Hom theory. In this paper it is shown that when the background theory is acyclic Hom and its pseudo-completion is unit refutable, there is a polynomial time algorithm for fmding minimal explanations. A test for unit-refutability of clausal theories is presented, based on the topology of the connection graph of the theory.

Kave Eshghi. 1993. A Tractable Class of Abduction Problems. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93. IJCAI, 3–7. https://ijcai.org/proceedings/1993/1

@inproceedings{ijcai1993p1,
  title     = {A Tractable Class of Abduction Problems},
  author    = {Eshghi, Kave},
  booktitle = {Proceedings of the Thirteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-93}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ruzena Bajcsy},
  pages     = {3--7},
  year      = {1993},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1993/1},
}

TY  - CPAPER
TI  - A Tractable Class of Abduction Problems
AU  - Eshghi, Kave
T2  - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1993
SP  - 3
EP  - 7
UR  - https://ijcai.org/proceedings/1993/1
ER  -