Talks and Poster Presentations (with Proceedings-Entry):
M. Lackner, A. Pfandler:
"Fixed-Parameter Algorithms for Closed World Reasoning";
Talk: European Conference on Artificial Intelligence (ECAI),
Montpellier, France;
08-27-2012
- 08-31-2012; in: "Proceedings of the ECAI Conference",
L. Raedt, Ch. Bessiere, D. Dubois, P. Doherty, P. Frasconi, F. Heintz, P. Lucas (ed.);
IOS Press,
242
(2012),
ISBN: 978-1-61499-097-0;
492
- 497.
English abstract:
Closed world reasoning and circumscription are essential tasks in AI. However, their high computational complexity is a serious obstacle for their practical application. In this work we employ the framework of parameterized complexity theory in order to search for fixed-parameter algorithms. We consider eleven parameters describing different characteristics of the input. For several combinations of these parameters we are able to design efficient fixedparameter tractable algorithms. All our algorithms have a runtime only single-exponential in the parameters and linear in the input size. Furthermore, by providing parameterized hardness results we show that we have actually found all tractable fragments involving these eleven parameters. We hereby offer a complete picture of the parameterized complexity of brave closed world reasoning and circumscription.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.3233/978-1-61499-098-7-492
Created from the Publication Database of the Vienna University of Technology.