A Tractable Class of Abduction Problems
Abstract
The problem of finding a set of assumptions which explain a given proposition is in general NP-hard, even when the background theory is an acyclic Horn theory. In this paper it is shown that when the background theory is acyclic Horn and its pseudo-completion is unit refutable, there is a polynomial time algorithm for finding minimal explanations. A test for unit-refutability of clausal theories is presented, based on the topology of the connection graph of the theory.
Cite
Text
Eshghi. "A Tractable Class of Abduction Problems." International Joint Conference on Artificial Intelligence, 1993.Markdown
[Eshghi. "A Tractable Class of Abduction Problems." International Joint Conference on Artificial Intelligence, 1993.](https://mlanthology.org/ijcai/1993/eshghi1993ijcai-tractable/)BibTeX
@inproceedings{eshghi1993ijcai-tractable,
title = {{A Tractable Class of Abduction Problems}},
author = {Eshghi, Kave},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1993},
pages = {3-8},
url = {https://mlanthology.org/ijcai/1993/eshghi1993ijcai-tractable/}
}