Archive for Mathematical Logic 54 (5-6):685-710 (2015)

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 under standard complexity assumptions.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
ISBN(s)
DOI 10.1007/s00153-015-0435-x
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,391
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Philosophical Writings of Peirce.Charles S. Peirce - 1940 - New York: Dover Publications.
Parameterized Complexity Theory.J. Flum - 2007 - Bulletin of Symbolic Logic 13 (2):246-248.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Lewis Dichotomies in Many-Valued Logics.Simone Bova - 2012 - Studia Logica 100 (6):1271-1290.
Computation Models for Parameterized Complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Parameterized Counting Problems.Catherine McCartin - 2006 - Annals of Pure and Applied Logic 138 (1):147-182.
The Parameterized Complexity of Maximality and Minimality Problems.Yijia Chen & Jörg Flum - 2008 - Annals of Pure and Applied Logic 151 (1):22-61.
Sparse Parameterized Problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.
Adaptive Fuzzy Logics for Contextual Hedge Interpretation.Stephan der Waart van Gulivank - 2009 - Journal of Logic, Language and Information 18 (3).
Adaptive Fuzzy Logics for Contextual Hedge Interpretation.Stephan van der Waart van Gulik - 2009 - Journal of Logic, Language and Information 18 (3):333-356.
Parameterized Complexity Theory. [REVIEW]Thomas Schwentick - 2007 - Bulletin of Symbolic Logic 13 (2):246-247.

Analytics

Added to PP index
2015-09-03

Total views
4 ( #1,167,060 of 2,326,310 )

Recent downloads (6 months)
2 ( #433,912 of 2,326,310 )

How can I increase my downloads?

Downloads

My notes