liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On the parameterized complexity of non-monotonic logics
Leibniz University of Hannover, Germany.
Leibniz University of Hannover, Germany.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Leibniz University of Hannover, Germany.
Show others and affiliations
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
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, 685-710 p.
Keyword [en]
Abduction; Autoepistemic logic; Default logic; Circumscription; Parameterized complexity; Courcelles theorem; Monadic second order logic
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-120725DOI: 10.1007/s00153-015-0435-xISI: 000358581600013OAI: diva2:848268

Funding Agencies|DFG [VO 630/6-2, ME 4279/1-1]

Available from: 2015-08-24 Created: 2015-08-24 Last updated: 2015-08-24

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Archive for mathematical logic
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 36 hits
ReferencesLink to record
Permanent link

Direct link