Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
From MaRDI portal
Publication:2667835
DOI10.1016/j.artint.2021.103651OpenAlexW4226051860MaRDI QIDQ2667835
Publication date: 2 March 2022
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2021.103651
treewidthtree decompositioncomplexity analysisparameterized complexityanswer set programmingtreewidth-aware reductions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Negation by default and unstratifiable logic programs
- ASSAT: computing answer sets of a logic program by SAT solvers
- Answer set based design of knowledge systems
- Treewidth. Computations and approximations
- Which problems have strongly exponential complexity?
- Exploiting treewidth for projected model counting and its limits
- SAT-based local improvement for finding tree decompositions of small width
- On the computational cost of disjunctive logic programming: Propositional case
- Propositional semantics for disjunctive logic programs
- Practical access to dynamic programming on tree decompositions
- Algorithms for propositional model counting
- A multiparametric view on answer set programming
- Train scheduling with hybrid ASP
- Treewidth and counting projected answer sets
- Evaluation of disjunctive programs in WASP
- Answer set solving with bounded treewidth revisited
- \textsc{lp2normal} -- a normalization tool for extended logic programs
- Parametrized complexity theory.
- Taming high treewidth with abstraction, nested dynamic programming, and database technology
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Normalizing Cardinality Rules Using Merging and Sorting Constructions
- Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
- Solution Enumeration for Projected Boolean Search Problems
- Some (in)translatability results for normal logic programs and propositional theories
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Autoepistemic logic
- Clique-Width and Directed Width Measures for Answer-Set Programming
- Answer Set Programming Modulo Acyclicity*
- Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
- ASP-Core-2 Input Language Format
- selp: A Single-Shot Epistemic Logic Program Solver
- Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs
- eclingo : A Solver for Epistemic Logic Programs
- Lower Bounds for QBFs of Bounded Treewidth
- Multi-shot ASP solving with clingo
- The Impact of Treewidth on Grounding and Solving of Answer Set Programs
- Expansion-based QBF Solving on Tree Decompositions*
- Why are there so many loop formulas?
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- Parameterized Algorithms
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
This page was built for publication: Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
