Name
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. 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), unless P=NP. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-28332-1_33 | language and automata theory and applications |
Keywords | DocType | Volume |
autoepistemic logic,large class,fixed-parameter time,expansion existence problem,space efficient algorithm,parameterized complexity,extension existence problem,efficient fixed-parameter algorithm,implication problem,different parameterizations,default logic,artificial intelligent,computational complexity | Conference | abs/1110.0623 |
Citations | PageRank | References |
1 | 0.35 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arne Meier | 1 | 126 | 19.00 |
| Johannes Schmidt | 2 | 1 | 0.69 |
| Michael Thomas | 3 | 1 | 0.35 |
| Heribert Vollmer | 4 | 805 | 71.64 |