On the Parameterized Complexity of Default Logic and Autoepistemic Logic

Arne Meier, Johannes Schmidt, Michael Thomas, Heribert Vollmer

Abstract

We investigate the application of Courcelle’s Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems.
BibTeX
@inproceedings{meier2012parameterized,
  author = {Arne Meier and Johannes Schmidt and Michael Thomas and Heribert Vollmer},
  title = {{On the Parameterized Complexity of Default Logic and Autoepistemic Logic}},
  booktitle = {LATA},
  year = {2012},
  doi = {10.1007/978-3-642-28332-1\_33},
}

Loading related content...

Figure