Publications in Scientific Journals:
A. Pfandler, R. Pichler, S. Woltran:
"The complexity of handling minimal solutions in logic-based abduction";
Journal of Logic and Computation,
Logic-based abduction is an important reasoning method with many applications in Artificial Intelligence including diagnosis, planning, and configuration. The goal of an abduction problem is to find a `solution´, i.e., an explanation for some observed symptoms. Usually, many solutions exist, and one is often interested in minimal ones only. Previous definitions of `solutions´ to an abduction problem tacitly made an open-world assumption. However, as far as minimality is concerned, this assumption may not always lead to the desired behaviour. To overcome this problem, we propose a new definition of solutions based on a closed-world approach. Moreover, we also introduce a new variant of minimality where only a part of the hypotheses is subject to minimization. A thorough complexity analysis reveals the close relationship between these two new notions as well as the differences compared with previous notions of solutions.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Created from the Publication Database of the Vienna University of Technology.