Backdoors to tractable answer set programming
From MaRDI portal
Publication:2341833
DOI10.1016/j.artint.2014.12.001zbMath1328.68040OpenAlexW2180068027MaRDI QIDQ2341833
Johannes K. Fichte, Stefan Szeider
Publication date: 6 May 2015
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2014.12.001
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic programming (68N17)
Related Items
Backdoors to Normality for Disjunctive Logic Programs ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Backdoor Sets for CSP. ⋮ Augmenting tractable fragments of abstract argumentation ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Strong Backdoors for Default Logic ⋮ A multiparametric view on answer set programming ⋮ Backdoors to planning ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction
Uses Software
Cites Work
- SOFSEM 2005: Theory and Practice of Computer Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Infeasibility of instance compression and succinct PCPs for NP
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover
- Improved upper bounds for vertex cover
- A hybrid branch-and-bound approach for exact rational mixed-integer programming
- Negation by default and unstratifiable logic programs
- Some consequences of non-uniform conditions on uniform classes
- Graph minors. III. Planar tree-width
- ASSAT: computing answer sets of a logic program by SAT solvers
- Answer set programming based on propositional satisfiability
- Computational properties of argument systems satisfying graph-theoretic constraints
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Backdoor sets of quantified Boolean formulas
- The directed subgraph homeomorphism problem
- Transforming normal logic programs to constraint logic programs
- The complexity of propositional closed world reasoning and circumscription
- Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation
- Characterizations of the disjunctive well-founded semantics: Confluent calculi and iterated GCWA
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Extending and implementing the stable model semantics
- Augmenting tractable fragments of abstract argumentation
- Conflict-driven answer set solving: from theory to practice
- On the computational cost of disjunctive logic programming: Propositional case
- Propositional semantics for disjunctive logic programs
- Permanents, Pfaffian orientations, and even directed circuits
- Logic programs with stable model semantics as a constraint programming paradigm
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Limitations of restricted branching in clause learning
- Logic programming and nonmonotonic reasoning. 8th international conference, LPNMR 2005, Diamante, Italy, September 5--8, 2005. Proceedings.
- Solving \#SAT using vertex covers
- Parametrized complexity theory.
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Backdoors to Acyclic SAT
- Strong Backdoors to Nested Satisfiability
- Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
- Backdoors to Satisfaction
- Multi-Criteria Optimization in Answer Set Programming
- Team-building with answer set programming in the Gioia-Tauro seaport
- Backdoors to q-Horn
- Compact Translations of Non-disjunctive Answer Set Programs to Propositional Clauses
- Abstraction-Based Algorithm for 2QBF
- Empirical Study of the Anatomy of Modern Sat Solvers
- Detecting inconsistencies in large biological networks with answer set programming
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Complex optimization in answer set programming
- The even-path problem for graphs and digraphs
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
- On the complexity of feedback set problems in signed digraphs
- Tradeoffs in the Complexity of Backdoor Detection
- Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
- The effect of structural branching on the efficiency of clause learning SAT solving: An experimental study
- Computing Stable Models via Reductions to Difference Logic
- Belief Revision with Bounded Treewidth
- Horn clause queries and generalizations
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Graph minors. II. Algorithmic aspects of tree-width
- Negation as failure using tight derivations for general logic programs
- On self-transformable combinatorial problems
- The Semantics of Predicate Logic as a Programming Language
- Autoepistemic logic
- On the impact of stratification on the complexity of nonmonotonic reasoning
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- Tight logic programs
- NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
- A Dynamic-Programming Based ASP-Solver
- Logic Programming
- Logic Programming
- Feedback Vertex Set in Mixed Graphs
- The Good, the Bad, and the Odd: Cycles in Answer-Set Programs
- Parameterized Algorithms for Even Cycle Transversal
- Unfolding partiality and disjunctions in stable model semantics
- The DLV system for knowledge representation and reasoning
- Backdoors to Normality for Disjunctive Logic Programs
- Answer Set Programming for Single-Player Games in General Game Playing
- Unsatisfiability-based optimization in clasp
- Preprocessing of Complex Non-Ground Rules in Answer Set Programming
- Logic Programming and Nonmonotonic Reasoning
