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

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)
DOI 10.1007/s00153-015-0435-x
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,634
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.
A Logic for Default Reasoning.Ray Reiter - 1980 - Artificial Intelligence 13 (1-2):81-137.
Circumscription — A Form of Non-Monotonic Reasoning.John McCarthy - 1980 - Artificial Intelligence 13 (1-2):27–39.
Semantic Considerations on Nonmonotonic Logic.Robert C. Moore - 1985 - Artificial Intelligence 25 (1):75-94.

View all 10 references / 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.


Added to PP index

Total views
4 ( #1,286,651 of 2,533,681 )

Recent downloads (6 months)
2 ( #260,225 of 2,533,681 )

How can I increase my downloads?


My notes