On the parameterized complexity of non-monotonic logics
2015 (English)In: Archive for mathematical logic, ISSN 0933-5846, E-ISSN 1432-0665, Vol. 54, no 5-6, 685-710 p.Article in journal (Refereed) Published
We investigate the application of Courcelles theorem and the logspace version of Elberfeld et al. in the context of non-monotonic reasoning. Here we formalize the implication problem for propositional sets of formulas, the extension existence problem for default logic, the expansion existence problem for autoepistemic logic, the circumscriptive inference problem, as well as the abduction problem in monadic second order logic and thereby obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu, resp., XLnu) under standard complexity assumptions.
Place, publisher, year, edition, pages
Springer Verlag (Germany) , 2015. Vol. 54, no 5-6, 685-710 p.
Abduction; Autoepistemic logic; Default logic; Circumscription; Parameterized complexity; Courcelles theorem; Monadic second order logic
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-120725DOI: 10.1007/s00153-015-0435-xISI: 000358581600013OAI: oai:DiVA.org:liu-120725DiVA: diva2:848268
Funding Agencies|DFG [VO 630/6-2, ME 4279/1-1]2015-08-242015-08-242015-08-24