On the parameterized complexity of non-monotonic logics

DOI10.1007/S00153-015-0435-XMaRDI QIDQ494658zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

abductionmonadic second-order logiccircumscriptionCourcelle's theoremautoepistemic logicparametrised 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)

Recommendations

• On the parameterized complexity of default logic and autoepistemic logic
• scientific article; zbMATH DE number 6131588
• scientific article; zbMATH DE number 1453052
• Complexity Results for Nonmonotonic Logics
• A survey of complexity results for non-monotonic logics

Cites work

• scientific article; zbMATH DE number 478394 (Why is no real title available?)
• scientific article; zbMATH DE number 549992 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• scientific article; zbMATH DE number 6131588 (Why is no real title available?)
• A logic for default reasoning
• A partial k-arboretum of graphs with bounded treewidth
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Circumscription - a form of non-monotonic reasoning
• Complexity Results for Nonmonotonic Logics
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Fixed-parameter tractability of disjunction-free default reasoning
• Graph structure and monadic second-order logic. A language-theoretic approach
• Logic for Programming, Artificial Intelligence, and Reasoning
• Logic programs with stable model semantics as a constraint programming paradigm
• On the Space Complexity of Parameterized Problems
• On the relationship between circumscription and negation as failure
• Parametrized complexity theory.
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Semantical considerations on nonmonotonic logic
• Structure and importance of logspace-MOD class
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of logic-based abduction
• The complexity of minimal satisfiability problems
• The complexity of propositional closed world reasoning and circumscription
• The complexity of propositional implication
• The complexity of reasoning for fragments of autoepistemic logic
• The complexity of reasoning for fragments of default logic

Cited in

(11)

• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Default logic and bounded treewidth
• On the parameterized complexity of default logic and autoepistemic logic
• A multiparametric view on answer set programming
• The Logical Consequence Role in LPNMR: A Parameterized Computation Approach
• Strong Backdoors for Default Logic
• Complexity Results for Nonmonotonic Logics
• Strong backdoors for default logic
• Strong backdoors for default logic
• scientific article; zbMATH DE number 6131588 (Why is no real title available?)
• Nonmonotonicity in the framework of parametric logic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494658)