On the parameterized complexity of non-monotonic logics

DOI10.1007/s00153-015-0435-xzbMath1361.03036OpenAlexW1797840536WikidataQ57998282 ScholiaQ57998282MaRDI QIDQ494658

Yong-Cai Geng, Sumit K. Garg

Publication date: 1 September 2015

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-015-0435-x

zbMATH Keywords

monadic second-order logicautoepistemic logicabductioncircumscriptionCourcelle's theoremparametrised complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Logics of knowledge and belief (including belief change) (03B42) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (3)

Default logic and bounded treewidth ⋮ Strong Backdoors for Default Logic ⋮ A multiparametric view on answer set programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of propositional implication
• Semantical considerations on nonmonotonic logic
• On the relationship between circumscription and negation as failure
• A logic for default reasoning
• Circumscription - a form of non-monotonic reasoning
• A partial k-arboretum of graphs with bounded treewidth
• The complexity of propositional closed world reasoning and circumscription
• Fixed-parameter tractability of disjunction-free default reasoning
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• The complexity of minimal satisfiability problems
• Logic programs with stable model semantics as a constraint programming paradigm
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Parametrized complexity theory.
• The complexity of reasoning for fragments of default logic
• The Complexity of Reasoning for Fragments of Autoepistemic Logic
• Structure and importance of logspace-MOD class
• Complexity Results for Nonmonotonic Logics
• The complexity of logic-based abduction
• On the Space Complexity of Parameterized Problems
• Logic for Programming, Artificial Intelligence, and Reasoning
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: On the parameterized complexity of non-monotonic logics