Strong Backdoors for Default Logic

DOI10.1007/978-3-319-40970-2_4MaRDI QIDQ2818000zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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) Parameterized complexity, tractability and kernelization (68Q27) Logic in artificial intelligence (68T27)

Abstract: In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, identity). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-DP2 , or in para-NP, depending on the target class.

Recommendations

• Strong backdoors to nested satisfiability
• A Fault-Tolerant Default Logic
• Tradeoffs in the Complexity of Backdoor Detection
• Backdoors for linear temporal logic
• Backdoors for linear temporal logic
• scientific article; zbMATH DE number 140378
• Backdoors to q-Horn
• Backdoors to q-Horn
• Backdoor sets for CSP

Cites work

• A logic for default reasoning
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Augmenting tractable fragments of abstract argumentation
• Backdoors to normality for disjunctive logic programs
• Backdoors to satisfaction
• Backdoors to tractable answer set programming
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Circumscription - a form of non-monotonic reasoning
• Complexity Results for Nonmonotonic Logics
• Describing parameterized complexity classes
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Fixed-parameter tractable reductions to SAT
• Fundamentals of parameterized complexity
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 478394 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Non-monotonic logic. I
• On self-transformable combinatorial problems
• On the parameterized complexity of non-monotonic logics
• Parametrized complexity theory.
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time
• Satisfiability of acyclic and almost acyclic CNF formulas
• Semantical considerations on nonmonotonic logic
• Strong Backdoors for Default Logic
• The complexity of reasoning for fragments of autoepistemic logic
• The complexity of reasoning for fragments of default logic
• The complexity of satisfiability problems
• Theory and Applications of Satisfiability Testing
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(11)

• Backdoors for linear temporal logic
• A multiparametric view on answer set programming
• Backdoors to planning
• Strong Backdoors for Default Logic
• Backdoors for linear temporal logic
• The good, the bad, and the odd: cycles in answer-set programs
• Backdoors to normality for disjunctive logic programs
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Default logic and bounded treewidth
• Strong backdoors for default logic
• Strong backdoors for default logic

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

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