[Back]

R. Pichler, S. Woltran:
"The Complexity of Handling Minimal Solutions in Logic-Based Abduction";
Talk: ECAI 2010 - 19th European Conference on Artificial Intelligence, Lisbon, Portugal; 2010-08-16 - 2010-08-20; in: "Prooceedings of ECAI 2010 - 19th European Conference on Artificial Intelligence", H. Coelho, R. Studer, M. Woolridge (ed.); IOS Press, 215 (2010), ISBN: 978-1-60750-605-8; 895 - 900.

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 behavior. 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

http://dx.doi.org/10.3233/978-1-60750-606-5-895