On the parameterized complexity of non-monotonic logicsShow others and affiliations
2015 (English)In: Archive for mathematical logic, ISSN 0933-5846, E-ISSN 1432-0665, Vol. 54, no 5-6, p. 685-710Article in journal (Refereed) Published
Abstract [en]
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, p. 685-710
Keywords [en]
Abduction; Autoepistemic logic; Default logic; Circumscription; Parameterized complexity; Courcelles theorem; Monadic second order logic
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hj:diva-31614DOI: 10.1007/s00153-015-0435-xISI: 000358581600013Scopus ID: 2-s2.0-84938960398OAI: oai:DiVA.org:hj-31614DiVA, id: diva2:957126
Note
Funding Agencies|DFG [VO 630/6-2, ME 4279/1-1]
2015-08-242016-09-012018-01-10Bibliographically approved