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. (shrink)

The Local Computation Framework has been used to improve the efficiency of computation in various uncertainty formalisms. This paper shows how the framework can be used for the computation of logical deduction in two different ways; the first way involves embedding model structures in the framework; the second, and more direct, way involves embedding sets of formulae. This work can be applied to many of the logics developed for different kinds of reasoning, including predicate calculus, modal logics, possibilistic logics, probabilistic (...) logics and non-monotonic logics. (shrink)

The closed world assumption plays a fundamental role in the theory of deductive databases. On the other hand, multi-valued logics occupy a vast field in non-classical logics. Some questions are better explained and expressed in terms of such logics. To enhance the expressive power and the declarative ability of a deductive database, we extend various CWA formalizations, including the naive CWA, the generalized CWA and the careful CWA, to multi-valued logics. The basic idea is to embed logic formulae into some (...) polynomial ring. The extensions can be applied in a uniform manner to any finitely multi-valued logics. Therefore they have also computational interest. (shrink)