Strong Backdoors for Default Logic

DOI10.1007/978-3-319-40970-2_4zbMath1475.68366arXiv1602.06052OpenAlexW2284542945WikidataQ57998270 ScholiaQ57998270MaRDI QIDQ2818000

Johannes K. Fichte, Arne Meier, Irina Schindler

Publication date: 5 September 2016

Published in: Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06052

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Default logic and bounded treewidth ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Strong Backdoors for Default Logic ⋮ A multiparametric view on answer set programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Satisfiability of acyclic and almost acyclic CNF formulas
• On the parameterized complexity of non-monotonic logics
• Improved upper bounds for vertex cover
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Semantical considerations on nonmonotonic logic
• A logic for default reasoning
• Circumscription - a form of non-monotonic reasoning
• Non-monotonic logic. I
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Augmenting tractable fragments of abstract argumentation
• Describing parameterized complexity classes
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Backdoors to tractable answer set programming
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Strong Backdoors for Default Logic
• The complexity of reasoning for fragments of default logic
• Backdoors to Satisfaction
• The Complexity of Reasoning for Fragments of Autoepistemic Logic
• Fixed-Parameter Tractable Reductions to SAT
• On self-transformable combinatorial problems
• Complexity Results for Nonmonotonic Logics
• Backdoors to Normality for Disjunctive Logic Programs
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems

This page was built for publication: Strong Backdoors for Default Logic