Name
Abstract | ||
|---|---|---|
We investigate the application of Courcelle's 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00153-015-0435-x | Archive for Mathematical Logic |
Keywords | Field | DocType |
Abduction, Autoepistemic logic, Default logic, Circumscription, Parameterized complexity, Courcelle’s theorem, Monadic second order logic | Default logic,Discrete mathematics,Autoepistemic logic,Courcelle's theorem,Second-order logic,Algebra,Non-monotonic logic,Many-valued logic,Monadic predicate calculus,Intermediate logic,Mathematics | Journal |
Volume | Issue | ISSN |
54 | 5-6 | 1432-0665 |
Citations | PageRank | References |
2 | 0.38 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arne Meier | 1 | 126 | 19.00 |
| Irina Schindler | 2 | 3 | 1.42 |
| Johannes Schmidt | 3 | 13 | 3.00 |
| Michael Thomas | 4 | 32 | 3.22 |
| Heribert Vollmer | 5 | 805 | 71.64 |