On the parameterized complexity of non-monotonic logics

DOI10.1007/S00153-015-0435-XzbMATH Open1361.03036DBLPjournals/aml/MeierS0TV15OpenAlexW1797840536WikidataQ57998282 ScholiaQ57998282MaRDI QIDQ494658FDOQ494658

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

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

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)

Cites Work

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

Cited In (11)

• Strong backdoors for default logic
• Strong Backdoors for Default Logic
• The Logical Consequence Role in LPNMR: A Parameterized Computation Approach
• Complexity Results for Nonmonotonic Logics
• Nonmonotonicity in the framework of parametric logic
• A multiparametric view on answer set programming
• Strong backdoors for default logic
• Title not available (Why is that?)
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Default logic and bounded treewidth
• On the parameterized complexity of default logic and autoepistemic 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)